#include <bits/stdc++.h>
#define INF 1000000000
#define ll long long
#define MAX_N 300005
using namespace std;
struct SegmentTree{
ll s = 0;
SegmentTree * left = NULL, * right = NULL;
SegmentTree(int l,int r,vector<int> &a){
if(l == r){
s = (ll)a[l];
}else{
int mid = (l+r)/2;
left = new SegmentTree(l,mid,a);
right = new SegmentTree(mid+1,r,a);
s = left->s + right->s;
}
}
void upd(int l,int r,int p,int k){
if(l == p && r == p){
s += k;
//cout << l << ' ' << r << ' ' << s << endl;
}
else{
int mid = (l+r)/2;
if(p <= mid)
left->upd(l,mid,p,k);
else
right->upd(mid+1,r,p,k);
s = left->s + right->s;
}
}
ll rsq(int l,int r,int ss,int e){
if(l >= ss && r <= e)
return s;
else if(l > e || r < ss)
return 0;
else{
int mid = (l+r)/2;
return left->rsq(l,mid,ss,e) + right->rsq(mid+1,r,ss,e);
}
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
ll h[n];
set<ll> s;
map<ll,int> trlt;
for(int i = 0; i < n; i++){
cin >> h[i];
s.insert(h[i]);
}
int c = 0;
for(auto x : s){
trlt[x] = c++;
}
for(int i = 0; i < n; i++){
h[i] = trlt[h[i]];
}
vector<int> a(MAX_N+1,0);
SegmentTree st_left(0,MAX_N,a);
for(int i = 0; i < n; i++){
a[h[i]]++;
}
SegmentTree st_right(0,MAX_N,a);
st_left.upd(0,MAX_N,h[0],1);
st_right.upd(0,MAX_N,h[0],-1);
st_right.upd(0,MAX_N,h[1],-1);
ll ans = 0;
for(int i = 1; i < n-1; i++){
if(h[i] > 0) ans += st_left.rsq(0,MAX_N,0,h[i]-1) * st_right.rsq(0,MAX_N,0,h[i]-1);
st_left.upd(0,MAX_N,h[i],1);
st_right.upd(0,MAX_N,h[i+1],-1);
}
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
39040 KB |
Output is correct |
2 |
Correct |
364 ms |
74344 KB |
Output is correct |
3 |
Correct |
372 ms |
79828 KB |
Output is correct |
4 |
Correct |
370 ms |
79836 KB |
Output is correct |
5 |
Correct |
365 ms |
79832 KB |
Output is correct |
6 |
Correct |
372 ms |
79948 KB |
Output is correct |
7 |
Correct |
375 ms |
79820 KB |
Output is correct |
8 |
Correct |
370 ms |
79996 KB |
Output is correct |
9 |
Correct |
301 ms |
63896 KB |
Output is correct |
10 |
Correct |
302 ms |
64032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
41408 KB |
Output is correct |
2 |
Correct |
126 ms |
41460 KB |
Output is correct |
3 |
Correct |
126 ms |
41412 KB |
Output is correct |
4 |
Correct |
121 ms |
41416 KB |
Output is correct |
5 |
Correct |
129 ms |
41400 KB |
Output is correct |
6 |
Correct |
130 ms |
41408 KB |
Output is correct |
7 |
Correct |
128 ms |
41320 KB |
Output is correct |
8 |
Correct |
118 ms |
41312 KB |
Output is correct |
9 |
Correct |
124 ms |
41496 KB |
Output is correct |
10 |
Correct |
45 ms |
38944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
41408 KB |
Output is correct |
2 |
Correct |
126 ms |
41460 KB |
Output is correct |
3 |
Correct |
126 ms |
41412 KB |
Output is correct |
4 |
Correct |
121 ms |
41416 KB |
Output is correct |
5 |
Correct |
129 ms |
41400 KB |
Output is correct |
6 |
Correct |
130 ms |
41408 KB |
Output is correct |
7 |
Correct |
128 ms |
41320 KB |
Output is correct |
8 |
Correct |
118 ms |
41312 KB |
Output is correct |
9 |
Correct |
124 ms |
41496 KB |
Output is correct |
10 |
Correct |
45 ms |
38944 KB |
Output is correct |
11 |
Correct |
187 ms |
41416 KB |
Output is correct |
12 |
Correct |
171 ms |
42272 KB |
Output is correct |
13 |
Correct |
180 ms |
42284 KB |
Output is correct |
14 |
Correct |
174 ms |
42188 KB |
Output is correct |
15 |
Correct |
174 ms |
42172 KB |
Output is correct |
16 |
Correct |
188 ms |
42280 KB |
Output is correct |
17 |
Correct |
181 ms |
42276 KB |
Output is correct |
18 |
Correct |
153 ms |
42184 KB |
Output is correct |
19 |
Correct |
154 ms |
42272 KB |
Output is correct |
20 |
Correct |
43 ms |
39028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
39076 KB |
Output is correct |
2 |
Correct |
42 ms |
39084 KB |
Output is correct |
3 |
Correct |
48 ms |
39032 KB |
Output is correct |
4 |
Correct |
43 ms |
39116 KB |
Output is correct |
5 |
Correct |
42 ms |
39096 KB |
Output is correct |
6 |
Correct |
42 ms |
39008 KB |
Output is correct |
7 |
Correct |
42 ms |
39028 KB |
Output is correct |
8 |
Correct |
43 ms |
38988 KB |
Output is correct |
9 |
Correct |
42 ms |
38968 KB |
Output is correct |
10 |
Correct |
43 ms |
38940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
39076 KB |
Output is correct |
2 |
Correct |
42 ms |
39084 KB |
Output is correct |
3 |
Correct |
48 ms |
39032 KB |
Output is correct |
4 |
Correct |
43 ms |
39116 KB |
Output is correct |
5 |
Correct |
42 ms |
39096 KB |
Output is correct |
6 |
Correct |
42 ms |
39008 KB |
Output is correct |
7 |
Correct |
42 ms |
39028 KB |
Output is correct |
8 |
Correct |
43 ms |
38988 KB |
Output is correct |
9 |
Correct |
42 ms |
38968 KB |
Output is correct |
10 |
Correct |
43 ms |
38940 KB |
Output is correct |
11 |
Correct |
58 ms |
40360 KB |
Output is correct |
12 |
Correct |
70 ms |
40324 KB |
Output is correct |
13 |
Correct |
55 ms |
40300 KB |
Output is correct |
14 |
Correct |
55 ms |
40324 KB |
Output is correct |
15 |
Correct |
67 ms |
40412 KB |
Output is correct |
16 |
Correct |
53 ms |
40324 KB |
Output is correct |
17 |
Correct |
55 ms |
40368 KB |
Output is correct |
18 |
Correct |
55 ms |
39720 KB |
Output is correct |
19 |
Correct |
48 ms |
39216 KB |
Output is correct |
20 |
Correct |
42 ms |
39012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
41408 KB |
Output is correct |
2 |
Correct |
126 ms |
41460 KB |
Output is correct |
3 |
Correct |
126 ms |
41412 KB |
Output is correct |
4 |
Correct |
121 ms |
41416 KB |
Output is correct |
5 |
Correct |
129 ms |
41400 KB |
Output is correct |
6 |
Correct |
130 ms |
41408 KB |
Output is correct |
7 |
Correct |
128 ms |
41320 KB |
Output is correct |
8 |
Correct |
118 ms |
41312 KB |
Output is correct |
9 |
Correct |
124 ms |
41496 KB |
Output is correct |
10 |
Correct |
45 ms |
38944 KB |
Output is correct |
11 |
Correct |
187 ms |
41416 KB |
Output is correct |
12 |
Correct |
171 ms |
42272 KB |
Output is correct |
13 |
Correct |
180 ms |
42284 KB |
Output is correct |
14 |
Correct |
174 ms |
42188 KB |
Output is correct |
15 |
Correct |
174 ms |
42172 KB |
Output is correct |
16 |
Correct |
188 ms |
42280 KB |
Output is correct |
17 |
Correct |
181 ms |
42276 KB |
Output is correct |
18 |
Correct |
153 ms |
42184 KB |
Output is correct |
19 |
Correct |
154 ms |
42272 KB |
Output is correct |
20 |
Correct |
43 ms |
39028 KB |
Output is correct |
21 |
Correct |
484 ms |
53552 KB |
Output is correct |
22 |
Correct |
507 ms |
53596 KB |
Output is correct |
23 |
Correct |
494 ms |
53452 KB |
Output is correct |
24 |
Correct |
501 ms |
53544 KB |
Output is correct |
25 |
Correct |
481 ms |
53436 KB |
Output is correct |
26 |
Correct |
496 ms |
53548 KB |
Output is correct |
27 |
Correct |
482 ms |
53468 KB |
Output is correct |
28 |
Correct |
244 ms |
53644 KB |
Output is correct |
29 |
Correct |
253 ms |
53532 KB |
Output is correct |
30 |
Correct |
44 ms |
39040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
39040 KB |
Output is correct |
2 |
Correct |
364 ms |
74344 KB |
Output is correct |
3 |
Correct |
372 ms |
79828 KB |
Output is correct |
4 |
Correct |
370 ms |
79836 KB |
Output is correct |
5 |
Correct |
365 ms |
79832 KB |
Output is correct |
6 |
Correct |
372 ms |
79948 KB |
Output is correct |
7 |
Correct |
375 ms |
79820 KB |
Output is correct |
8 |
Correct |
370 ms |
79996 KB |
Output is correct |
9 |
Correct |
301 ms |
63896 KB |
Output is correct |
10 |
Correct |
302 ms |
64032 KB |
Output is correct |
11 |
Correct |
127 ms |
41408 KB |
Output is correct |
12 |
Correct |
126 ms |
41460 KB |
Output is correct |
13 |
Correct |
126 ms |
41412 KB |
Output is correct |
14 |
Correct |
121 ms |
41416 KB |
Output is correct |
15 |
Correct |
129 ms |
41400 KB |
Output is correct |
16 |
Correct |
130 ms |
41408 KB |
Output is correct |
17 |
Correct |
128 ms |
41320 KB |
Output is correct |
18 |
Correct |
118 ms |
41312 KB |
Output is correct |
19 |
Correct |
124 ms |
41496 KB |
Output is correct |
20 |
Correct |
45 ms |
38944 KB |
Output is correct |
21 |
Correct |
187 ms |
41416 KB |
Output is correct |
22 |
Correct |
171 ms |
42272 KB |
Output is correct |
23 |
Correct |
180 ms |
42284 KB |
Output is correct |
24 |
Correct |
174 ms |
42188 KB |
Output is correct |
25 |
Correct |
174 ms |
42172 KB |
Output is correct |
26 |
Correct |
188 ms |
42280 KB |
Output is correct |
27 |
Correct |
181 ms |
42276 KB |
Output is correct |
28 |
Correct |
153 ms |
42184 KB |
Output is correct |
29 |
Correct |
154 ms |
42272 KB |
Output is correct |
30 |
Correct |
43 ms |
39028 KB |
Output is correct |
31 |
Correct |
49 ms |
39076 KB |
Output is correct |
32 |
Correct |
42 ms |
39084 KB |
Output is correct |
33 |
Correct |
48 ms |
39032 KB |
Output is correct |
34 |
Correct |
43 ms |
39116 KB |
Output is correct |
35 |
Correct |
42 ms |
39096 KB |
Output is correct |
36 |
Correct |
42 ms |
39008 KB |
Output is correct |
37 |
Correct |
42 ms |
39028 KB |
Output is correct |
38 |
Correct |
43 ms |
38988 KB |
Output is correct |
39 |
Correct |
42 ms |
38968 KB |
Output is correct |
40 |
Correct |
43 ms |
38940 KB |
Output is correct |
41 |
Correct |
58 ms |
40360 KB |
Output is correct |
42 |
Correct |
70 ms |
40324 KB |
Output is correct |
43 |
Correct |
55 ms |
40300 KB |
Output is correct |
44 |
Correct |
55 ms |
40324 KB |
Output is correct |
45 |
Correct |
67 ms |
40412 KB |
Output is correct |
46 |
Correct |
53 ms |
40324 KB |
Output is correct |
47 |
Correct |
55 ms |
40368 KB |
Output is correct |
48 |
Correct |
55 ms |
39720 KB |
Output is correct |
49 |
Correct |
48 ms |
39216 KB |
Output is correct |
50 |
Correct |
42 ms |
39012 KB |
Output is correct |
51 |
Correct |
484 ms |
53552 KB |
Output is correct |
52 |
Correct |
507 ms |
53596 KB |
Output is correct |
53 |
Correct |
494 ms |
53452 KB |
Output is correct |
54 |
Correct |
501 ms |
53544 KB |
Output is correct |
55 |
Correct |
481 ms |
53436 KB |
Output is correct |
56 |
Correct |
496 ms |
53548 KB |
Output is correct |
57 |
Correct |
482 ms |
53468 KB |
Output is correct |
58 |
Correct |
244 ms |
53644 KB |
Output is correct |
59 |
Correct |
253 ms |
53532 KB |
Output is correct |
60 |
Correct |
44 ms |
39040 KB |
Output is correct |
61 |
Correct |
861 ms |
79780 KB |
Output is correct |
62 |
Correct |
881 ms |
79860 KB |
Output is correct |
63 |
Correct |
855 ms |
79848 KB |
Output is correct |
64 |
Correct |
873 ms |
79832 KB |
Output is correct |
65 |
Correct |
915 ms |
79832 KB |
Output is correct |
66 |
Correct |
885 ms |
79904 KB |
Output is correct |
67 |
Correct |
933 ms |
79832 KB |
Output is correct |
68 |
Correct |
725 ms |
63988 KB |
Output is correct |
69 |
Correct |
590 ms |
57580 KB |
Output is correct |
70 |
Correct |
40 ms |
38984 KB |
Output is correct |