Submission #961100

#TimeUsernameProblemLanguageResultExecution timeMemory
961100PetyIzbori (COCI22_izbori)C++14
110 / 110
593 ms8016 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int INF = 1e9; const int MOD = 1e9 + 7; int n, a[250002]; ll sol; int idk[500005]; void divide (int st, int dr) { if (st == dr) { sol += 1; return; } int mid = (st + dr) / 2; divide(st, mid); divide(mid + 1, dr); map<int, int>fr; set<int>Maj; for (int i = mid; i >= st; i--) { fr[a[i]]++; if (fr[a[i]] >= (mid - i + 1) / 2 + 1) Maj.insert(a[i]); } fr.clear(); for (int i = mid + 1; i <= dr; i++) { fr[a[i]]++; if (fr[a[i]] >= (i - mid) / 2 + 1) Maj.insert(a[i]); } int lim = (dr - st + 1); for (auto val : Maj) { int nr = 0; for (int i = mid; i >= st; i--) { if (a[i] == val) nr++; else nr--; idk[nr + lim]++; } for (int i = 2*lim; i >= 0; i--) idk[i] += idk[i + 1]; nr = 0; for (int i = mid + 1; i <= dr; i++) { if (a[i] == val) nr++; else nr--; sol += idk[-nr + lim + 1]; } for (int i = 2*lim; i >= 0; i--) idk[i] = 0; } } int main () { //ios_base::sync_with_stdio(false); //cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; divide(1, n); cout << sol; 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...