# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1092389 | 2024-09-24T01:21:36 Z | huyy123 | Mountains (NOI20_mountains) | C++14 | 133 ms | 15564 KB |
#include<bits/stdc++.h> #define fi first #define se second #define ll long long #define ld long double #define pii pair<int,int> #define SZ(x) ((int)(x.size())) #define bit(i,x) ((x>>i)&1) #define pb push_back #define int long long #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define FORD(i,a,b) for(int i=(a);i>=(b);--i) #define task "test" using namespace std; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); ll Rand(ll l,ll r){assert(l<=r);return uniform_int_distribution<ll>(l,r)(rd);} const int MAXn=5e5+7; const int MOD=1e9+7; const ll oo = 1e18; const ll BASE=3137LL; int n,a[MAXn],dp[MAXn],res; struct FenwickTree{ int f[MAXn]; int N; void init(int n){FOR(i,1,n)f[i]=0;N=n;} void upd(int idx,int val){ for(idx;idx<=N;idx+=(idx&-idx)){ f[idx]+=val; } } int get(int idx){ int ans=0; for(idx;idx>=1;idx-=(idx&-idx)){ ans+=f[idx]; } return ans; } }ft; void solution(){ cin>>n; vector<int>zip; FOR(i,1,n)cin>>a[i],zip.pb(a[i]); sort(zip.begin(),zip.end()); zip.resize(unique(zip.begin(),zip.end())-zip.begin()); FOR(i,1,n)a[i]=lower_bound(zip.begin(),zip.end(),a[i])-zip.begin()+1; ft.init(n); FOR(i,1,n){ dp[i]=ft.get(a[i]-1); ft.upd(a[i],1); } ft.init(n); FORD(i,n,1){ res+=dp[i]*ft.get(a[i]-1); ft.upd(a[i],1); } cout<<res; } int32_t main(){ if(fopen(task".inp","r")){freopen(task".inp","r",stdin);freopen(task".out","w",stdout);} ios_base::sync_with_stdio(0);cin.tie(0); int ntest=1;//cin>>ntest; while(ntest--){solution();} cerr<<"\n"<<1.0*clock()/CLOCKS_PER_SEC<<"s "; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 63 ms | 15040 KB | Output is correct |
3 | Correct | 69 ms | 15396 KB | Output is correct |
4 | Correct | 80 ms | 15300 KB | Output is correct |
5 | Correct | 62 ms | 15292 KB | Output is correct |
6 | Correct | 62 ms | 15288 KB | Output is correct |
7 | Correct | 63 ms | 15396 KB | Output is correct |
8 | Correct | 63 ms | 15296 KB | Output is correct |
9 | Correct | 63 ms | 15500 KB | Output is correct |
10 | Correct | 65 ms | 15564 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 10440 KB | Output is correct |
2 | Correct | 48 ms | 10436 KB | Output is correct |
3 | Correct | 50 ms | 10432 KB | Output is correct |
4 | Correct | 50 ms | 10552 KB | Output is correct |
5 | Correct | 51 ms | 10436 KB | Output is correct |
6 | Correct | 49 ms | 10440 KB | Output is correct |
7 | Correct | 52 ms | 10436 KB | Output is correct |
8 | Correct | 49 ms | 10488 KB | Output is correct |
9 | Correct | 44 ms | 10444 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 10440 KB | Output is correct |
2 | Correct | 48 ms | 10436 KB | Output is correct |
3 | Correct | 50 ms | 10432 KB | Output is correct |
4 | Correct | 50 ms | 10552 KB | Output is correct |
5 | Correct | 51 ms | 10436 KB | Output is correct |
6 | Correct | 49 ms | 10440 KB | Output is correct |
7 | Correct | 52 ms | 10436 KB | Output is correct |
8 | Correct | 49 ms | 10488 KB | Output is correct |
9 | Correct | 44 ms | 10444 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 59 ms | 10644 KB | Output is correct |
12 | Correct | 56 ms | 10704 KB | Output is correct |
13 | Correct | 57 ms | 10692 KB | Output is correct |
14 | Correct | 56 ms | 10692 KB | Output is correct |
15 | Correct | 61 ms | 10684 KB | Output is correct |
16 | Correct | 58 ms | 10692 KB | Output is correct |
17 | Correct | 57 ms | 10640 KB | Output is correct |
18 | Correct | 40 ms | 10704 KB | Output is correct |
19 | Correct | 47 ms | 10780 KB | Output is correct |
20 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 3 ms | 1116 KB | Output is correct |
12 | Correct | 3 ms | 1036 KB | Output is correct |
13 | Correct | 4 ms | 1120 KB | Output is correct |
14 | Correct | 3 ms | 1116 KB | Output is correct |
15 | Correct | 4 ms | 1548 KB | Output is correct |
16 | Correct | 3 ms | 1036 KB | Output is correct |
17 | Correct | 3 ms | 1368 KB | Output is correct |
18 | Correct | 3 ms | 1036 KB | Output is correct |
19 | Correct | 2 ms | 860 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 10440 KB | Output is correct |
2 | Correct | 48 ms | 10436 KB | Output is correct |
3 | Correct | 50 ms | 10432 KB | Output is correct |
4 | Correct | 50 ms | 10552 KB | Output is correct |
5 | Correct | 51 ms | 10436 KB | Output is correct |
6 | Correct | 49 ms | 10440 KB | Output is correct |
7 | Correct | 52 ms | 10436 KB | Output is correct |
8 | Correct | 49 ms | 10488 KB | Output is correct |
9 | Correct | 44 ms | 10444 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 59 ms | 10644 KB | Output is correct |
12 | Correct | 56 ms | 10704 KB | Output is correct |
13 | Correct | 57 ms | 10692 KB | Output is correct |
14 | Correct | 56 ms | 10692 KB | Output is correct |
15 | Correct | 61 ms | 10684 KB | Output is correct |
16 | Correct | 58 ms | 10692 KB | Output is correct |
17 | Correct | 57 ms | 10640 KB | Output is correct |
18 | Correct | 40 ms | 10704 KB | Output is correct |
19 | Correct | 47 ms | 10780 KB | Output is correct |
20 | Correct | 0 ms | 344 KB | Output is correct |
21 | Correct | 101 ms | 11640 KB | Output is correct |
22 | Correct | 111 ms | 11636 KB | Output is correct |
23 | Correct | 103 ms | 11636 KB | Output is correct |
24 | Correct | 101 ms | 11636 KB | Output is correct |
25 | Correct | 104 ms | 11632 KB | Output is correct |
26 | Correct | 105 ms | 11708 KB | Output is correct |
27 | Correct | 103 ms | 11716 KB | Output is correct |
28 | Correct | 45 ms | 11608 KB | Output is correct |
29 | Correct | 45 ms | 11692 KB | Output is correct |
30 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 63 ms | 15040 KB | Output is correct |
3 | Correct | 69 ms | 15396 KB | Output is correct |
4 | Correct | 80 ms | 15300 KB | Output is correct |
5 | Correct | 62 ms | 15292 KB | Output is correct |
6 | Correct | 62 ms | 15288 KB | Output is correct |
7 | Correct | 63 ms | 15396 KB | Output is correct |
8 | Correct | 63 ms | 15296 KB | Output is correct |
9 | Correct | 63 ms | 15500 KB | Output is correct |
10 | Correct | 65 ms | 15564 KB | Output is correct |
11 | Correct | 54 ms | 10440 KB | Output is correct |
12 | Correct | 48 ms | 10436 KB | Output is correct |
13 | Correct | 50 ms | 10432 KB | Output is correct |
14 | Correct | 50 ms | 10552 KB | Output is correct |
15 | Correct | 51 ms | 10436 KB | Output is correct |
16 | Correct | 49 ms | 10440 KB | Output is correct |
17 | Correct | 52 ms | 10436 KB | Output is correct |
18 | Correct | 49 ms | 10488 KB | Output is correct |
19 | Correct | 44 ms | 10444 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 59 ms | 10644 KB | Output is correct |
22 | Correct | 56 ms | 10704 KB | Output is correct |
23 | Correct | 57 ms | 10692 KB | Output is correct |
24 | Correct | 56 ms | 10692 KB | Output is correct |
25 | Correct | 61 ms | 10684 KB | Output is correct |
26 | Correct | 58 ms | 10692 KB | Output is correct |
27 | Correct | 57 ms | 10640 KB | Output is correct |
28 | Correct | 40 ms | 10704 KB | Output is correct |
29 | Correct | 47 ms | 10780 KB | Output is correct |
30 | Correct | 0 ms | 344 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 0 ms | 348 KB | Output is correct |
33 | Correct | 0 ms | 344 KB | Output is correct |
34 | Correct | 1 ms | 348 KB | Output is correct |
35 | Correct | 0 ms | 348 KB | Output is correct |
36 | Correct | 0 ms | 348 KB | Output is correct |
37 | Correct | 0 ms | 348 KB | Output is correct |
38 | Correct | 0 ms | 348 KB | Output is correct |
39 | Correct | 0 ms | 348 KB | Output is correct |
40 | Correct | 0 ms | 348 KB | Output is correct |
41 | Correct | 3 ms | 1116 KB | Output is correct |
42 | Correct | 3 ms | 1036 KB | Output is correct |
43 | Correct | 4 ms | 1120 KB | Output is correct |
44 | Correct | 3 ms | 1116 KB | Output is correct |
45 | Correct | 4 ms | 1548 KB | Output is correct |
46 | Correct | 3 ms | 1036 KB | Output is correct |
47 | Correct | 3 ms | 1368 KB | Output is correct |
48 | Correct | 3 ms | 1036 KB | Output is correct |
49 | Correct | 2 ms | 860 KB | Output is correct |
50 | Correct | 0 ms | 348 KB | Output is correct |
51 | Correct | 101 ms | 11640 KB | Output is correct |
52 | Correct | 111 ms | 11636 KB | Output is correct |
53 | Correct | 103 ms | 11636 KB | Output is correct |
54 | Correct | 101 ms | 11636 KB | Output is correct |
55 | Correct | 104 ms | 11632 KB | Output is correct |
56 | Correct | 105 ms | 11708 KB | Output is correct |
57 | Correct | 103 ms | 11716 KB | Output is correct |
58 | Correct | 45 ms | 11608 KB | Output is correct |
59 | Correct | 45 ms | 11692 KB | Output is correct |
60 | Correct | 0 ms | 348 KB | Output is correct |
61 | Correct | 132 ms | 15296 KB | Output is correct |
62 | Correct | 126 ms | 15292 KB | Output is correct |
63 | Correct | 130 ms | 15528 KB | Output is correct |
64 | Correct | 129 ms | 15292 KB | Output is correct |
65 | Correct | 131 ms | 15336 KB | Output is correct |
66 | Correct | 131 ms | 15296 KB | Output is correct |
67 | Correct | 133 ms | 15288 KB | Output is correct |
68 | Correct | 124 ms | 15332 KB | Output is correct |
69 | Correct | 103 ms | 11712 KB | Output is correct |
70 | Correct | 0 ms | 348 KB | Output is correct |