Submission #866306

#TimeUsernameProblemLanguageResultExecution timeMemory
866306TAhmed33Izbori (COCI22_izbori)C++98
110 / 110
127 ms12932 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") #pragma GCC target ("popcnt") typedef long long ll; inline ll trig (ll x) { return ((x * (x + 1)) >> 1); } inline ll get2 (ll a, ll b, ll c) { if (c < 0) return 0; a = min(a, c); b = min(b, c); c = min(c, a + b); return (c - b) * (b + 1) + (c + 1) * (a - c + b + 1) - trig(a) + trig(c - b - 1); } const int MAXN = 2e5 + 25; int arr[MAXN], n; vector <int> occ[MAXN]; vector <int> d; int a[2 * MAXN + 25]; ll solve1 (int x) { memset(a, 0, sizeof(a)); ll ret = 0; int cur = 0; int sum = 0; a[MAXN] = 1; for (int i = 1; i <= n; i++) { if (arr[i] == x) { sum++; cur += a[sum - 1 + MAXN]; } else { cur -= a[sum - 1 + MAXN]; sum--; } ret += cur; a[sum + MAXN]++; } return ret; } array <int, 500> p; ll solve2 (int x) { for (int i = 0; i < (int)occ[x].size(); i++) p[i] = occ[x][i]; int u = occ[x].size(); ll ret = 0; //cout << x << ": \n"; for (int i = 0; i < u - 1; i++) { for (int j = i + 1; j < u; j++) { if (2 * (j - i + 1) - 2 - p[j] + p[i] < 0) continue; ret += get2(p[i] - (i == 0 ? 0 : p[i - 1]) - 1, (j == u - 1 ? n + 1 : p[j + 1]) - p[j] - 1, 2 * (j - i + 1) - 2 - p[j] + p[i]); //cout << ret << '\n'; if (j - i + 1 <= (p[j] - p[i] + 1) / 2) ret -= get2(p[i] - (i == 0 ? 0 : p[i - 1]) - 1, (j == u - 1 ? n + 1 : p[j + 1]) - p[j] - 1, (p[j] - p[i] + 1) / 2 - (j - i + 1)); //cout << i << " | " << j << " " << ret << '\n'; } } ret += u; return ret; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; d.push_back(arr[i]); } sort(d.begin(), d.end()); d.resize(unique(d.begin(), d.end()) - d.begin()); for (int i = 1; i <= n; i++) arr[i] = lower_bound(d.begin(), d.end(), arr[i]) - d.begin(); for (int i = 1; i <= n; i++) { occ[arr[i]].push_back(i); } bool flag = 1; for (int i = 1; i <= n; i++) flag |= (arr[i] <= 2); if (n >= 1e5 && !flag) return 0; ll sum = 0; int x = sqrt(n); while (x * x < n) x++; while (x * x > n) x--; for (int i = 0; i < n; i++) { if (occ[i].empty()) continue; if ((int)occ[i].size() > x) sum += solve1(i); else { sum += solve2(i); } } cout << sum << '\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...