# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883234 | 2023-12-04T20:28:26 Z | borisAngelov | Izbori (COCI22_izbori) | C++17 | 3000 ms | 12720 KB |
#include <bits/stdc++.h> using namespace std; const int maxn = 200005; int n; int a[maxn]; vector<int> byPosition[maxn]; void read() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; } } void compress() { vector<pair<int, int>> v; for (int i = 1; i <= n; ++i) { v.push_back(make_pair(a[i], i)); } sort(v.begin(), v.end()); int maxNumber = 0; for (int i = 0; i < v.size(); ++i) { if (i == 0 || v[i].first != v[i - 1].first) { ++maxNumber; } a[v[i].second] = maxNumber; } } int b[maxn]; int pref[maxn]; struct FenwickTree { int tree[2 * maxn]; void reset() { for (int i = 1; i <= 2 * n; ++i) { tree[i] = 0; } } void update(int pos, int val) { for (int i = pos; i <= 2 * n; i += (i & (-i))) { tree[i] += val; } } int query(int pos) { int result = 0; for (int i = pos; i >= 1; i -= (i & (-i))) { result += tree[i]; } return result; } }; FenwickTree tree; void solve() { compress(); for (int i = 1; i <= n; ++i) { byPosition[a[i]].push_back(i); } long long ans = 0; for (int i = 1; i <= n; ++i) { if (byPosition[i].empty() == true) { continue; } for (int j = 1; j <= n; ++j) { b[j] = -1; } for (int j = 0; j < byPosition[i].size(); ++j) { b[byPosition[i][j]] = +1; } tree.reset(); tree.update(n, +1); for (int j = 1; j <= n; ++j) { pref[j] = pref[j - 1] + b[j]; tree.update(pref[j] + n, +1); ans += tree.query(pref[j] + n - 1); } } cout << ans << endl; } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); read(); solve(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6492 KB | Output is correct |
2 | Correct | 1 ms | 6492 KB | Output is correct |
3 | Correct | 1 ms | 6492 KB | Output is correct |
4 | Correct | 1 ms | 6628 KB | Output is correct |
5 | Correct | 2 ms | 6492 KB | Output is correct |
6 | Correct | 1 ms | 6492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6492 KB | Output is correct |
2 | Correct | 1 ms | 6492 KB | Output is correct |
3 | Correct | 1 ms | 6492 KB | Output is correct |
4 | Correct | 1 ms | 6628 KB | Output is correct |
5 | Correct | 2 ms | 6492 KB | Output is correct |
6 | Correct | 1 ms | 6492 KB | Output is correct |
7 | Correct | 9 ms | 6680 KB | Output is correct |
8 | Correct | 2 ms | 6488 KB | Output is correct |
9 | Correct | 3 ms | 6492 KB | Output is correct |
10 | Correct | 2 ms | 6492 KB | Output is correct |
11 | Correct | 2 ms | 6492 KB | Output is correct |
12 | Correct | 2 ms | 6488 KB | Output is correct |
13 | Correct | 2 ms | 6492 KB | Output is correct |
14 | Correct | 2 ms | 6492 KB | Output is correct |
15 | Correct | 2 ms | 6492 KB | Output is correct |
16 | Correct | 2 ms | 6636 KB | Output is correct |
17 | Correct | 1 ms | 6492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 10180 KB | Output is correct |
2 | Correct | 29 ms | 10552 KB | Output is correct |
3 | Correct | 16 ms | 9768 KB | Output is correct |
4 | Correct | 31 ms | 10564 KB | Output is correct |
5 | Correct | 33 ms | 10392 KB | Output is correct |
6 | Correct | 34 ms | 10680 KB | Output is correct |
7 | Correct | 39 ms | 10700 KB | Output is correct |
8 | Correct | 36 ms | 10912 KB | Output is correct |
9 | Correct | 35 ms | 10680 KB | Output is correct |
10 | Correct | 34 ms | 10676 KB | Output is correct |
11 | Correct | 21 ms | 11184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6492 KB | Output is correct |
2 | Correct | 1 ms | 6492 KB | Output is correct |
3 | Correct | 1 ms | 6492 KB | Output is correct |
4 | Correct | 1 ms | 6628 KB | Output is correct |
5 | Correct | 2 ms | 6492 KB | Output is correct |
6 | Correct | 1 ms | 6492 KB | Output is correct |
7 | Correct | 9 ms | 6680 KB | Output is correct |
8 | Correct | 2 ms | 6488 KB | Output is correct |
9 | Correct | 3 ms | 6492 KB | Output is correct |
10 | Correct | 2 ms | 6492 KB | Output is correct |
11 | Correct | 2 ms | 6492 KB | Output is correct |
12 | Correct | 2 ms | 6488 KB | Output is correct |
13 | Correct | 2 ms | 6492 KB | Output is correct |
14 | Correct | 2 ms | 6492 KB | Output is correct |
15 | Correct | 2 ms | 6492 KB | Output is correct |
16 | Correct | 2 ms | 6636 KB | Output is correct |
17 | Correct | 1 ms | 6492 KB | Output is correct |
18 | Correct | 24 ms | 10180 KB | Output is correct |
19 | Correct | 29 ms | 10552 KB | Output is correct |
20 | Correct | 16 ms | 9768 KB | Output is correct |
21 | Correct | 31 ms | 10564 KB | Output is correct |
22 | Correct | 33 ms | 10392 KB | Output is correct |
23 | Correct | 34 ms | 10680 KB | Output is correct |
24 | Correct | 39 ms | 10700 KB | Output is correct |
25 | Correct | 36 ms | 10912 KB | Output is correct |
26 | Correct | 35 ms | 10680 KB | Output is correct |
27 | Correct | 34 ms | 10676 KB | Output is correct |
28 | Correct | 21 ms | 11184 KB | Output is correct |
29 | Correct | 28 ms | 12720 KB | Output is correct |
30 | Execution timed out | 3048 ms | 10064 KB | Time limit exceeded |
31 | Halted | 0 ms | 0 KB | - |