Submission #654695

#	Time	Username	Problem	Language	Result	Execution time	Memory
654695		Valera_Grinenko	Election (BOI18_election)	C++17	0 / 100	2 ms	468 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());
struct node {
  bool id = 0;
  //fixed -> no negative pref sum
  //not fixed -> any pref sum
  int fixed_ans = 0;
  int fixed_sum = 0;
  int sum = 0;
  int fixed_mn_suf = 0;
  int mn_suf = 0;
  int mn_pref = 0;
};
node comb(node a, node b) {
  node c;
  if(a.id) return b;
  if(b.id) return a;
  c.sum = a.sum + b.sum;
  c.mn_suf = min(b.mn_suf, a.mn_suf + b.sum);
  c.mn_pref = min(a.mn_pref, b.mn_pref + a.sum);
  int add = 0;
  if(a.fixed_sum + b.mn_pref < 0) add = -(a.fixed_sum + b.mn_pref);
  c.fixed_sum = a.fixed_sum + b.sum + add;
  c.fixed_ans = a.fixed_ans + add;
  c.fixed_mn_suf = min(b.mn_suf + add, a.fixed_mn_suf + b.sum + add);
  return c;
}
node idnode;
const int N = 5e5 + 42;
node st[4 * N];
string s;
void build(int v, int tl, int tr) {
  if(tl == tr) {
    if(s[tl] == 'C') {
      st[v].fixed_ans = 0;
      st[v].fixed_sum = 1;
      st[v].sum = 1;
      st[v].fixed_mn_suf = 0;
      st[v].mn_suf = 0;
      st[v].mn_pref = 0;
    } else {
      st[v].fixed_ans = 1;
      st[v].fixed_sum = 0;
      st[v].sum = -1;
      st[v].fixed_mn_suf = 0;
      st[v].mn_suf = -1;
      st[v].mn_pref = -1;
    }
  } else {
    int tm = (tl + tr) / 2;
    build((v << 1), tl, tm);
    build((v << 1) + 1, tm + 1, tr);
    st[v] = comb(st[(v << 1)], st[(v << 1) + 1]);
  }
}
node get(int v, int tl, int tr, int l, int r) {
  if(l > r) return idnode;
  if(l == tl && r == tr) return st[v];
  int tm = (tl + tr) / 2;
  return comb(get((v << 1), tl, tm, l, min(r, tm)), get((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}
void solve() {
  int n, q;
  cin >> n;
  cin >> s;
  build(1, 0, n - 1);
  cin >> q;
  while(q--) {
    int l, r;
    cin >> l >> r; l--; r--;
    node res = get(1, 0, n - 1, l, r);
    cout << res.fixed_ans - res.fixed_mn_suf << '\n';
  }
}
int main() {

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

  idnode.id = 1;

  int t = 1;

  // cin >> t;

  while(t--) solve();

  return 0;
}
/*

*/

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