Submission #654687

#	Time	Username	Problem	Language	Result	Execution time	Memory
654687		Valera_Grinenko	Election (BOI18_election)	C++17	28 / 100	3079 ms	1416 KiB

election

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
  int n, q;
  cin >> n;
  string s; cin >> s;
  cin >> q;
  while(q--) {
    vector<int> done(n);
    int l, r;
    cin >> l >> r; l--; r--;
    int pref = 0;
    int ans = 0;
    for(int i = l; i <= r; i++) {
      if(s[i] == 'C') pref++;
      else {
        if(!pref) { done[i] = 1; ans++; }
        else pref--;
      }
    }
    int mn_pref = 0; pref = 0;
    for(int i = r; i >= l; i--)
      if(!done[i]) {
        if(s[i] == 'C') pref++;
        else {
          pref--;
          mn_pref = min(mn_pref, pref);
        }
      }
    cout << ans - mn_pref << '\n';
  }
}
int main() {

  ios::sync_with_stdio(0); cin.tie(0);

  int t = 1;

  // cin >> t;

  while(t--) solve();

  return 0;
}
/*

*/

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