Submission #1215332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215332		lopkus	Election (BOI18_election)	C++20	28 / 100	3093 ms	952 KiB

election

#include <bits/stdc++.h>

signed main() {
  int n;
  std::cin >> n;
  std::string c;
  std::cin >> c;
  std::vector<char> a(n + 1);
  for(int i = 1; i <= n; i++) {
    a[i] = c[i - 1];
  }
  int q;
  std::cin >> q;
  while(q--) {
    int l, r;
    std::cin >> l >> r;
    int pref = 0;
    std::vector<int> was(n + 1);
    int ans = 0;
    for(int i = l; i <= r; i++) {
      pref += (a[i] == 'C' ? 1 : - 1);
      if(pref < 0) {
        was[i] = 1;
        ans += 1;
        pref += 1;
      }
    }
    pref = 0;
    for(int i = r; i >= l; i--) {
      if(was[i]) {
        continue;
      }
      pref += (a[i] == 'C' ? 1 : - 1);
      if(pref < 0) {
        was[i] = 1;
        ans += 1;
        pref += 1;
      }
    }
    std::cout << ans << "\n";
  }
}

• Subtask 1: 28 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18