# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1066311 | 2024-08-19T17:43:30 Z | tamthegod | Mountains (NOI20_mountains) | C++17 | 171 ms | 19176 KB |
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, a[maxN]; vector<int> vc; struct BIT { vector<int> bit; int n; void init(int _n) { n = _n; bit.resize(n + 5, 0); } void update(int pos, int val) { for(; pos <= n; pos += (pos & (-pos))) bit[pos] += val; } int get(int pos) { int res = 0; for(; pos; pos -= (pos & (-pos))) res += bit[pos]; return res; } }; void ReadInput() { cin >> n; for(int i=1; i<=n; i++) { cin >> a[i]; vc.pb(a[i]); } sort(vc.begin(), vc.end()); vc.erase(unique(vc.begin(), vc.end()), vc.end()); for(int i=1; i<=n; i++) a[i] = upper_bound(vc.begin(), vc.end(), a[i]) - vc.begin(); } void Solve() { BIT pref, suff; pref.init(n); suff.init(n); for(int i=2; i<=n; i++) suff.update(a[i], 1); pref.update(a[1], 1); int res = 0; for(int i=2; i<n; i++) { suff.update(a[i], - 1); res += pref.get(a[i] - 1) * suff.get(a[i] - 1); pref.update(a[i], 1); } cout << res; } #define taskname "" int32_t main() { if (fopen(taskname ".inp", "r")) { freopen(taskname ".inp", "r", stdin); freopen(taskname ".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); int T = 1; //cin >> T; for(int itest=1; itest<=T; itest++) { ReadInput(); Solve(); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 115 ms | 17852 KB | Output is correct |
3 | Correct | 85 ms | 18624 KB | Output is correct |
4 | Correct | 88 ms | 17304 KB | Output is correct |
5 | Correct | 84 ms | 17444 KB | Output is correct |
6 | Correct | 87 ms | 17600 KB | Output is correct |
7 | Correct | 111 ms | 19124 KB | Output is correct |
8 | Correct | 84 ms | 17356 KB | Output is correct |
9 | Correct | 91 ms | 18504 KB | Output is correct |
10 | Correct | 97 ms | 19176 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 99 ms | 12492 KB | Output is correct |
2 | Correct | 99 ms | 13776 KB | Output is correct |
3 | Correct | 89 ms | 12484 KB | Output is correct |
4 | Correct | 89 ms | 13520 KB | Output is correct |
5 | Correct | 87 ms | 12324 KB | Output is correct |
6 | Correct | 87 ms | 12484 KB | Output is correct |
7 | Correct | 99 ms | 13508 KB | Output is correct |
8 | Correct | 95 ms | 13636 KB | Output is correct |
9 | Correct | 77 ms | 12496 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 99 ms | 12492 KB | Output is correct |
2 | Correct | 99 ms | 13776 KB | Output is correct |
3 | Correct | 89 ms | 12484 KB | Output is correct |
4 | Correct | 89 ms | 13520 KB | Output is correct |
5 | Correct | 87 ms | 12324 KB | Output is correct |
6 | Correct | 87 ms | 12484 KB | Output is correct |
7 | Correct | 99 ms | 13508 KB | Output is correct |
8 | Correct | 95 ms | 13636 KB | Output is correct |
9 | Correct | 77 ms | 12496 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 93 ms | 12992 KB | Output is correct |
12 | Correct | 90 ms | 14016 KB | Output is correct |
13 | Correct | 89 ms | 12740 KB | Output is correct |
14 | Correct | 86 ms | 13592 KB | Output is correct |
15 | Correct | 94 ms | 12992 KB | Output is correct |
16 | Correct | 94 ms | 12904 KB | Output is correct |
17 | Correct | 96 ms | 12744 KB | Output is correct |
18 | Correct | 73 ms | 12772 KB | Output is correct |
19 | Correct | 77 ms | 14196 KB | Output is correct |
20 | Correct | 0 ms | 604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 480 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 | 344 KB | Output is correct |
8 | Correct | 1 ms | 600 KB | Output is correct |
9 | Correct | 1 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 | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 480 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 | 344 KB | Output is correct |
8 | Correct | 1 ms | 600 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 3 ms | 856 KB | Output is correct |
12 | Correct | 3 ms | 860 KB | Output is correct |
13 | Correct | 3 ms | 860 KB | Output is correct |
14 | Correct | 3 ms | 856 KB | Output is correct |
15 | Correct | 4 ms | 860 KB | Output is correct |
16 | Correct | 3 ms | 860 KB | Output is correct |
17 | Correct | 3 ms | 860 KB | Output is correct |
18 | Correct | 3 ms | 860 KB | Output is correct |
19 | Correct | 2 ms | 860 KB | Output is correct |
20 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 99 ms | 12492 KB | Output is correct |
2 | Correct | 99 ms | 13776 KB | Output is correct |
3 | Correct | 89 ms | 12484 KB | Output is correct |
4 | Correct | 89 ms | 13520 KB | Output is correct |
5 | Correct | 87 ms | 12324 KB | Output is correct |
6 | Correct | 87 ms | 12484 KB | Output is correct |
7 | Correct | 99 ms | 13508 KB | Output is correct |
8 | Correct | 95 ms | 13636 KB | Output is correct |
9 | Correct | 77 ms | 12496 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 93 ms | 12992 KB | Output is correct |
12 | Correct | 90 ms | 14016 KB | Output is correct |
13 | Correct | 89 ms | 12740 KB | Output is correct |
14 | Correct | 86 ms | 13592 KB | Output is correct |
15 | Correct | 94 ms | 12992 KB | Output is correct |
16 | Correct | 94 ms | 12904 KB | Output is correct |
17 | Correct | 96 ms | 12744 KB | Output is correct |
18 | Correct | 73 ms | 12772 KB | Output is correct |
19 | Correct | 77 ms | 14196 KB | Output is correct |
20 | Correct | 0 ms | 604 KB | Output is correct |
21 | Correct | 116 ms | 13584 KB | Output is correct |
22 | Correct | 121 ms | 14428 KB | Output is correct |
23 | Correct | 132 ms | 14784 KB | Output is correct |
24 | Correct | 146 ms | 14984 KB | Output is correct |
25 | Correct | 120 ms | 14544 KB | Output is correct |
26 | Correct | 122 ms | 13560 KB | Output is correct |
27 | Correct | 144 ms | 15040 KB | Output is correct |
28 | Correct | 71 ms | 13508 KB | Output is correct |
29 | Correct | 73 ms | 15048 KB | Output is correct |
30 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 115 ms | 17852 KB | Output is correct |
3 | Correct | 85 ms | 18624 KB | Output is correct |
4 | Correct | 88 ms | 17304 KB | Output is correct |
5 | Correct | 84 ms | 17444 KB | Output is correct |
6 | Correct | 87 ms | 17600 KB | Output is correct |
7 | Correct | 111 ms | 19124 KB | Output is correct |
8 | Correct | 84 ms | 17356 KB | Output is correct |
9 | Correct | 91 ms | 18504 KB | Output is correct |
10 | Correct | 97 ms | 19176 KB | Output is correct |
11 | Correct | 99 ms | 12492 KB | Output is correct |
12 | Correct | 99 ms | 13776 KB | Output is correct |
13 | Correct | 89 ms | 12484 KB | Output is correct |
14 | Correct | 89 ms | 13520 KB | Output is correct |
15 | Correct | 87 ms | 12324 KB | Output is correct |
16 | Correct | 87 ms | 12484 KB | Output is correct |
17 | Correct | 99 ms | 13508 KB | Output is correct |
18 | Correct | 95 ms | 13636 KB | Output is correct |
19 | Correct | 77 ms | 12496 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 93 ms | 12992 KB | Output is correct |
22 | Correct | 90 ms | 14016 KB | Output is correct |
23 | Correct | 89 ms | 12740 KB | Output is correct |
24 | Correct | 86 ms | 13592 KB | Output is correct |
25 | Correct | 94 ms | 12992 KB | Output is correct |
26 | Correct | 94 ms | 12904 KB | Output is correct |
27 | Correct | 96 ms | 12744 KB | Output is correct |
28 | Correct | 73 ms | 12772 KB | Output is correct |
29 | Correct | 77 ms | 14196 KB | Output is correct |
30 | Correct | 0 ms | 604 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 348 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 1 ms | 480 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 | 344 KB | Output is correct |
38 | Correct | 1 ms | 600 KB | Output is correct |
39 | Correct | 1 ms | 348 KB | Output is correct |
40 | Correct | 0 ms | 348 KB | Output is correct |
41 | Correct | 3 ms | 856 KB | Output is correct |
42 | Correct | 3 ms | 860 KB | Output is correct |
43 | Correct | 3 ms | 860 KB | Output is correct |
44 | Correct | 3 ms | 856 KB | Output is correct |
45 | Correct | 4 ms | 860 KB | Output is correct |
46 | Correct | 3 ms | 860 KB | Output is correct |
47 | Correct | 3 ms | 860 KB | Output is correct |
48 | Correct | 3 ms | 860 KB | Output is correct |
49 | Correct | 2 ms | 860 KB | Output is correct |
50 | Correct | 0 ms | 344 KB | Output is correct |
51 | Correct | 116 ms | 13584 KB | Output is correct |
52 | Correct | 121 ms | 14428 KB | Output is correct |
53 | Correct | 132 ms | 14784 KB | Output is correct |
54 | Correct | 146 ms | 14984 KB | Output is correct |
55 | Correct | 120 ms | 14544 KB | Output is correct |
56 | Correct | 122 ms | 13560 KB | Output is correct |
57 | Correct | 144 ms | 15040 KB | Output is correct |
58 | Correct | 71 ms | 13508 KB | Output is correct |
59 | Correct | 73 ms | 15048 KB | Output is correct |
60 | Correct | 0 ms | 344 KB | Output is correct |
61 | Correct | 142 ms | 17520 KB | Output is correct |
62 | Correct | 171 ms | 18996 KB | Output is correct |
63 | Correct | 145 ms | 18364 KB | Output is correct |
64 | Correct | 155 ms | 18816 KB | Output is correct |
65 | Correct | 163 ms | 19140 KB | Output is correct |
66 | Correct | 138 ms | 18108 KB | Output is correct |
67 | Correct | 137 ms | 17996 KB | Output is correct |
68 | Correct | 142 ms | 18992 KB | Output is correct |
69 | Correct | 130 ms | 15300 KB | Output is correct |
70 | Correct | 0 ms | 344 KB | Output is correct |