제출 #654716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654716		Valera_Grinenko	Election (BOI18_election)	C++17	100 / 100	485 ms	20568 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 {
  int ans = 0;
  int sum = 0;
  int mx_suf = 0;
  int mx_pref = 0;
};
inline node comb(node a, node b) {
  node c;
  if(a.ans == -1) return b;
  if(b.ans == -1) return a;
  c.ans = max(max(a.ans + b.sum, b.ans + a.sum), a.mx_pref + b.mx_suf);
  c.sum = a.sum + b.sum;
  c.mx_suf = max(b.mx_suf, a.mx_suf + b.sum);
  c.mx_pref = max(a.mx_pref, b.mx_pref + a.sum);
  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].ans = 0;
      st[v].sum = -1;
      st[v].mx_suf = 0;
      st[v].mx_pref = 0;
    } else {
      st[v].ans = 1;
      st[v].sum = 1;
      st[v].mx_suf = 1;
      st[v].mx_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.ans << '\n';
  }
}
int main() {

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

  idnode.ans = -1;

  int t = 1;

  // cin >> t;

  while(t--) solve();

  return 0;
}
/*

*/

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