Submission #532356

#	Time	Username	Problem	Language	Result	Execution time	Memory
532356		Alex_tz307	Izbori (COCI22_izbori)	C++17	110 / 110	142 ms	6980 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int kN = 1 << 18;
int a[kN];
int64_t ans, f[kN << 1];
bitset<kN> used;

void solve(int l, int r) {
  if (l == r) {
    ++ans;
    return;
  }
  int mid = (l + r) >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  vector<int> candidates;
  for (int i = l; i <= r; ++i) {
    f[a[i]] = 0;
    used[a[i]] = false;
  }
  for (int i = mid; i >= l; --i) {
    if (++f[a[i]] > (mid - i + 1) / 2 && !used[a[i]]) {
      candidates.emplace_back(a[i]);
      used[a[i]] = true;
    }
  }
  for (int i = l; i <= mid; ++i) {
    f[a[i]] = 0;
  }
  for (int i = mid + 1; i <= r; ++i) {
    if (++f[a[i]] > (i - mid) / 2 && !used[a[i]]) {
      candidates.emplace_back(a[i]);
      used[a[i]] = true;
    }
  }
  int len = r - l + 1;
  for (const int &x : candidates) {
    for (int i = -len - 1; i <= len + 1; ++i) {
      f[i + kN] = 0;
    }
    int sum = 0;
    for (int i = mid; i >= l; --i) {
      if (a[i] == x) {
        ++sum;
      } else {
        --sum;
      }
      ++f[sum + kN];
    }
    for (int i = len; i >= -len - 1; --i) {
      f[i + kN] += f[i + 1 + kN];
    }
    sum = 0;
    for (int i = mid + 1; i <= r; ++i) {
      if (a[i] == x) {
        ++sum;
      } else {
        --sum;
      }
      ans += f[-sum + 1 + kN];
    }
  }
}

void testCase() {
  int n;
  cin >> n;
  vector<int> v;
  v.resize(n);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    v[i - 1] = a[i];
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 1; i <= n; ++i) {
    a[i] = distance(v.begin(), lower_bound(v.begin(), v.end(), a[i]));
  }
  solve(1, n);
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    testCase();
  }
  return 0;
}

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