Submission #1142755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142755		aykhn	Izbori (COCI22_izbori)	C++20	110 / 110	162 ms	15432 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 2e5 + 5;
const int B = 450;

int freq[MXN * 2];

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int a[n];
  for (int &i : a) cin >> i;
  map<int, vector<int>> mp;
  for (int i = 0; i < n; i++) mp[a[i]].push_back(i);
  int res = 0;
  for (auto &[val, idx] : mp)
  {
    if (idx.size() < B)
    {
      for (int i = 0; i < idx.size(); i++)
      {
        for (int j = i; j < idx.size(); j++)
        {
          int sz = idx[j] - idx[i] + 1, cnt = j - i + 1;
          if (cnt * 2 <= sz) continue;
          int C = cnt * 2 - sz - 1;
          int A = min(C, idx[i] - (i ? idx[i - 1] : -1) - 1);
          int B = min(C, (j + 1 < idx.size() ? idx[j + 1] : n) - idx[j] - 1); 
          int l1 = 0, r1 = C - B - 1;
          int l2 = C - B, r2 = A;
          l1 = max(0LL, l1), r1 = min(r1, A);
          l2 = max(0LL, l2), r2 = min(r2, A);
          if (l1 <= r1) res += (r1 - l1 + 1) * (B + 1);
          if (l2 <= r2)
          {
            res += (C + 1) * (r2 - l2 + 1);
            res -= (l2 + r2) * (r2 - l2 + 1) / 2;
          }
        }
      }
    }
    else
    {
      for (int &i : a) i = -1;
      for (int &i : idx) a[i] = 1;
      int cur = 0, S = 0;
      freq[0 + MXN] = 1;
      int L = MXN, R = MXN;
      for (int &i : a)
      {
        if (i == 1)
        {
          cur += freq[S + MXN];
          S++;
        }
        else
        {
          cur -= freq[S - 1 + MXN];
          S--;
        }
        res += cur;
        freq[S + MXN]++;
        L = min(L, S + MXN), R = max(R, S + MXN);
      }
      for (int i = L; i <= R; i++) freq[i] = 0;
    }
  }
  cout << res << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 70 / 70