제출 #751263

#제출 시각아이디문제언어결과실행 시간메모리
751263stevancvIzbori (COCI22_izbori)C++14
10 / 110
1006 ms9472 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 4e5 + 5; const int S = 400; const int inf = 1e9; int n; struct Fenwick { int bit[N]; void Reset(int n) { for (int i = 1; i <= 2 * n + 1; i++) bit[i] = 0; } void Add(int x) { x += n + 1; for (; x < N; x += x & (-x)) bit[x] += 1; } int Get(int x) { int ans = 0; x += n; for (; x > 0; x -= x & (-x)) ans += bit[x]; return ans; } }f; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; map<int, int> hsh; int z = 0; vector<int> a(n); vector<vector<int>> pos(n); for (int i = 0; i < n; i++) { cin >> a[i]; if (hsh.find(a[i]) == hsh.end()) hsh[a[i]] = z++; a[i] = hsh[a[i]]; pos[a[i]].push_back(i); } vector<int> big(n); for (int i = 0; i < n; i++) if (pos[i].size() >= S) big[i] = 1; ll ans = 0; vector<int> cnt(n); for (int i = 0; i < n; i++) { int mx = a[i]; for (int j = i; j >= max(0, i - 2 * S); j--) { cnt[a[j]] += 1; if (cnt[a[j]] > cnt[mx]) mx = a[j]; if (2 * cnt[mx] > i - j + 1 && big[mx] == 0) ans += 1; } for (int j = i; j >= max(0, i - 2 * S); j--) cnt[a[j]] = 0; } for (int p = 0; p < n; p++) { if (big[p] == 0) continue; vector<int> pref(n); f.Reset(n); f.Add(0); for (int i = 0; i < n; i++) { if (a[i] == p) pref[i] += 1; else pref[i] -= 1; if (i > 0) pref[i] += pref[i - 1]; ans += f.Get(pref[i]); f.Add(pref[i]); cout << p << sp << i << endl; } } cout << ans << en; 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...