제출 #907485

#제출 시각아이디문제언어결과실행 시간메모리
907485TranGiaHuy1508Izbori (COCI22_izbori)C++17
0 / 110
45 ms6868 KiB
#include <bits/stdc++.h> using namespace std; void main_program(); signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); main_program(); } #define int long long int n, threshold; vector<int> v; map<int, int> compress, mpcnt; int solve_light(vector<int> &V){ vector<int> CNT(n + 1); int res = 0; for (int l = 0; l < n; l++){ int mx = 0; for (int r = l; r <= min(n - 1, l + threshold * 2); r++){ if (V[r] >= 0) mx = max(mx, ++CNT[V[r]]); if (mx * 2 > (r - l + 1)){ res++; } } for (int r = l; r <= min(n - 1, l + threshold * 2); r++){ CNT[V[r]]--; } } return res; } int solve_heavy(vector<int> &V){ vector<int> dp(n * 2 + 5, 0), cnt(n * 2 + 5, 0); int res = 0; int pfx = n + 2; cnt[pfx]++; for (int i = 0; i < n; i++){ pfx += V[i]; cnt[pfx]++; dp[pfx] = dp[pfx - 1] + cnt[pfx - 1]; res += dp[pfx]; } return res; } void main_program(){ cin >> n; v.resize(n); threshold = sqrt(n); for (int i = 0; i < n; i++){ cin >> v[i]; mpcnt[v[i]]++; compress[v[i]] = 1; } int crr = 1; for (auto &[key, value]: compress) value = crr++; for (auto &key: v) key = compress[key]; int res = 0; for (auto [key, value]: mpcnt){ if (value > threshold){ vector<int> vec(n); int newkey = compress[key]; for (int i = 0; i < n; i++) vec[i] = (v[i] == newkey) ? 1 : -1; res += solve_heavy(vec); } } int bruhbruh = -1; for (int i = 0; i < n; i++){ if (mpcnt[v[i]] > threshold){ v[i] = --bruhbruh; } } res += solve_light(v); cout << res << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...