88038
525000372 80012714 109225034 202750922 130487539 728482754 12221732 415580934 676277240 62820
<870707 bytes omitted>用户输出
827480
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #63284 | #1294. 小巨人 | Accepted | 100 | 1344 ms | 8564 K | C++ / 1.1 K | waibiwaibi | 2021-07-22 16:14:00 |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
struct seg {
int maxx;
} tr[maxn << 2];
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
void push_up(int root) { tr[root].maxx = max(tr[root << 1].maxx, tr[root << 1 | 1].maxx); }
void build(int root, int l, int r) {
if (l == r) {
tr[root].maxx = -1;
return;
}
int mid = l + r >> 1;
build(lson);
build(rson);
push_up(root);
}
void modify(int root, int l, int r, int pos, int x) {
if (l == r && r == pos) {
tr[root].maxx = x;
return;
}
int mid = l + r >> 1;
if (pos <= mid)
modify(lson, pos, x);
else
modify(rson, pos, x);
push_up(root);
}
int query(int root, int l, int r, int x) {
if (tr[root].maxx < x)
return 0;
if (l == r)
return l;
int mid = l + r >> 1;
int L = root << 1, R = root << 1 | 1;
if (tr[R].maxx >= x)
return query(rson, x);
else
return query(lson, x);
}
int main() {
int n;
scanf("%d", &n);
long long ans = 0;
build(1, 1, n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
int tmp;
ans += i - 1 - (tmp = query(1, 1, n, x));
modify(1, 1, n, i, x);
// printf("i=%d %d\n",i,tmp);
}
printf("%lld\n", ans);
return 0;
}88038
525000372 80012714 109225034 202750922 130487539 728482754 12221732 415580934 676277240 62820
<870707 bytes omitted>用户输出
827480
系统信息
Exited with return code 0579587
856853027 491128544 890854354 153519960 984791609 206048293 825864731 757030299 454709263 71
<5731544 bytes omitted>用户输出
6654540
系统信息
Exited with return code 0332776
20214786 25643449 85875229 669189822 786830323 78956882 896957608 316275871 996659486 112043
<3290502 bytes omitted>用户输出
3640628
系统信息
Exited with return code 0378106
649277098 602235533 676791970 565157587 871478991 969866980 305951880 349922654 219356112 71
<3739348 bytes omitted>用户输出
4255686
系统信息
Exited with return code 050707
573885207 16269207 484510054 235771559 126486098 416813941 239447948 228122492 605078855 5606
<501320 bytes omitted>用户输出
454772
系统信息
Exited with return code 0718010
395903754 395576340 135364929 667873133 671849068 433013211 158510201 649491954 345164287 81
<7100232 bytes omitted>用户输出
8739603
系统信息
Exited with return code 0687980
359487458 74032531 780864892 968394410 12251982 7681806 193646009 858538586 146826885 130208
<6803076 bytes omitted>用户输出
8165253
系统信息
Exited with return code 0114647
704295242 692354435 905240998 987254045 310468104 743698300 292349193 960759587 489744508 39
<1133571 bytes omitted>用户输出
1145186
系统信息
Exited with return code 0781448
0 969 1941 2489 3864 4571 5811 6134 7960 7492 9437 10456 11609 12377 12968 13066 15126 14617
<7690522 bytes omitted>用户输出
1295853917
系统信息
Exited with return code 0