Submission #1266627

#TimeUsernameProblemLanguageResultExecution timeMemory
1266627canhnam357Izbori (COCI22_izbori)C++20
110 / 110
369 ms8972 KiB
#include <bits/stdc++.h> using namespace std; long long f(int l, int r) { return 1LL * (l + r) * (r - l + 1) / 2; } #define N 200'005 int bit[2 * N]{}, mark[2 * N]{}, timer = 0; void update(int pos, int val) { while (pos < 2 * N) { if (mark[pos] != timer) { mark[pos] = timer; bit[pos] = 0; } bit[pos] += val; pos += pos & -pos; } } int get(int pos) { int ans = 0; while (pos > 0) { if (mark[pos] != timer) { mark[pos] = timer; bit[pos] = 0; } ans += bit[pos]; pos -= pos & -pos; } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int &i : a) cin >> i; auto cc = a; sort(cc.begin(), cc.end()); cc.erase(unique(cc.begin(), cc.end()), cc.end()); for (int &i : a) { i = lower_bound(cc.begin(), cc.end(), i) - cc.begin(); } int m = cc.size(); const int B = 1000; vector<vector<int>> pos(m); for (int i = 0; i < n; i++) { pos[a[i]].push_back(i); } long long ans = n; for (int i = 0; i < m; i++) { timer++; if (pos[i].size() > B) { int sum = N; update(sum, 1); for (int j : a) { if (j == i) sum++; else sum--; ans += get(sum - 1); update(sum, 1); } ans -= pos[i].size(); } else { for (int l = 0; l < pos[i].size(); l++) { for (int r = l + 1; r < pos[i].size(); r++) { int bad = pos[i][r] - pos[i][l] - r + l; if (bad >= r - l + 1) continue; int lb = 0, rb = r - l - bad; int le = (l ? pos[i][l] - pos[i][l - 1] - 1 : pos[i][l]); int ri = (r + 1 == pos[i].size() ? n - 1 - pos[i][r] : pos[i][r + 1] - pos[i][r] - 1); le = min(le, rb); ri = min(ri, rb); ans += le + 1; if (rb <= ri) ans += f(rb - le, rb); else if (rb - le >= ri) ans += ri * (le + 1); else { ans += f(rb - le, ri); ans += (rb - ri) * ri; } } } } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...