oj.uz

Submission #654716

# Submission time Handle Problem Language Result Execution time Memory
654716 2022-11-01T10:32:30 Z Valera_Grinenko Election (BOI18_election) C++17
100 / 100
 485 ms 20568 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 53 ms 5028 KB Output is correct
7 Correct 59 ms 5096 KB Output is correct
8 Correct 48 ms 4972 KB Output is correct
9 Correct 44 ms 4968 KB Output is correct
10 Correct 51 ms 4940 KB Output is correct
11 Correct 49 ms 5136 KB Output is correct
12 Correct 49 ms 5132 KB Output is correct
13 Correct 50 ms 5240 KB Output is correct
14 Correct 50 ms 5084 KB Output is correct
15 Correct 61 ms 5020 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 53 ms 5028 KB Output is correct
7 Correct 59 ms 5096 KB Output is correct
8 Correct 48 ms 4972 KB Output is correct
9 Correct 44 ms 4968 KB Output is correct
10 Correct 51 ms 4940 KB Output is correct
11 Correct 49 ms 5136 KB Output is correct
12 Correct 49 ms 5132 KB Output is correct
13 Correct 50 ms 5240 KB Output is correct
14 Correct 50 ms 5084 KB Output is correct
15 Correct 61 ms 5020 KB Output is correct
16 Correct 439 ms 19528 KB Output is correct
17 Correct 451 ms 19544 KB Output is correct
18 Correct 440 ms 19576 KB Output is correct
19 Correct 343 ms 19096 KB Output is correct
20 Correct 485 ms 18560 KB Output is correct
21 Correct 458 ms 20568 KB Output is correct
22 Correct 441 ms 20436 KB Output is correct
23 Correct 442 ms 20564 KB Output is correct
24 Correct 453 ms 20276 KB Output is correct
25 Correct 441 ms 19768 KB Output is correct