oj.uz

Submission #359695

# Submission time Handle Problem Language Result Execution time Memory
359695 2021-01-27T06:39:21 Z vkgainz Election (BOI18_election) C++17
100 / 100
 746 ms 43080 KB 
#include <bits/stdc++.h>
using namespace std;
const int MX = 5e5 + 5;
struct node {
  int sum, ans, mn, mx;
  node() {
    sum = 0, ans = 0, mn = 0, mx = 0;
  }
  node(int a, int b, int c, int d):
    sum(a), ans(b), mn(c), mx(d)
  {
  }
} seg[4 * MX];
node comb(node &a, node &b) {
  node ret;
  ret.sum = a.sum+b.sum;
  ret.mn = min(a.mn, b.mn + a.sum);
  ret.mx = max(a.mx, b.mx + a.sum);
  ret.ans = max({a.ans - b.sum, b.ans-a.sum, b.mx + a.sum - a.mn - ret.sum});
  return ret;
}
int sz = 1;
void build(string &s, int n, int x=0, int lx=0, int rx=sz) {
  if(rx-lx==1) {
    if(lx<n) {
      if(s[lx]=='C') seg[x] = node(1, -1, 0, 1);
      else seg[x] = node(-1, 1, -1, 0);
    }
    else seg[x] = node();
    return;
  }
  int m = (lx+rx)/2;
  build(s, n, 2*x+1, lx, m), build(s, n, 2*x+2, m, rx);
  seg[x] = comb(seg[2*x+1], seg[2*x+2]);
}
node query(int l, int r,int x=0, int lx=0, int rx=sz) { //[l, r)
  if(lx>=r || rx<=l) return node();
  if(lx>=l && rx<=r) return seg[x];
  int m = (lx+rx)/2;
  node a = query(l, r, 2*x+1, lx, m), b = query(l, r, 2*x+2, m, rx);
  return comb(a, b);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n; cin >> n;
  while(sz<n) sz*=2;
  string s; cin >> s;
  build(s, n);
  int q; cin >> q;
  while(q--) {
    int l, r; cin >> l >> r;
    --l, --r;
    node x = query(l, r+1);
    cout << max(0, x.ans) << "\n";
  }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31724 KB Output is correct
2 Correct 22 ms 31596 KB Output is correct
3 Correct 23 ms 31596 KB Output is correct
4 Correct 22 ms 31596 KB Output is correct
5 Correct 22 ms 31596 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31724 KB Output is correct
2 Correct 22 ms 31596 KB Output is correct
3 Correct 23 ms 31596 KB Output is correct
4 Correct 22 ms 31596 KB Output is correct
5 Correct 22 ms 31596 KB Output is correct
6 Correct 89 ms 32108 KB Output is correct
7 Correct 88 ms 33064 KB Output is correct
8 Correct 94 ms 33132 KB Output is correct
9 Correct 85 ms 33004 KB Output is correct
10 Correct 91 ms 32960 KB Output is correct
11 Correct 89 ms 33132 KB Output is correct
12 Correct 88 ms 33132 KB Output is correct
13 Correct 88 ms 33132 KB Output is correct
14 Correct 89 ms 33132 KB Output is correct
15 Correct 91 ms 33004 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31724 KB Output is correct
2 Correct 22 ms 31596 KB Output is correct
3 Correct 23 ms 31596 KB Output is correct
4 Correct 22 ms 31596 KB Output is correct
5 Correct 22 ms 31596 KB Output is correct
6 Correct 89 ms 32108 KB Output is correct
7 Correct 88 ms 33064 KB Output is correct
8 Correct 94 ms 33132 KB Output is correct
9 Correct 85 ms 33004 KB Output is correct
10 Correct 91 ms 32960 KB Output is correct
11 Correct 89 ms 33132 KB Output is correct
12 Correct 88 ms 33132 KB Output is correct
13 Correct 88 ms 33132 KB Output is correct
14 Correct 89 ms 33132 KB Output is correct
15 Correct 91 ms 33004 KB Output is correct
16 Correct 708 ms 42072 KB Output is correct
17 Correct 603 ms 41600 KB Output is correct
18 Correct 717 ms 41856 KB Output is correct
19 Correct 551 ms 41472 KB Output is correct
20 Correct 706 ms 41088 KB Output is correct
21 Correct 714 ms 43008 KB Output is correct
22 Correct 697 ms 43008 KB Output is correct
23 Correct 746 ms 43080 KB Output is correct
24 Correct 713 ms 42876 KB Output is correct
25 Correct 722 ms 42240 KB Output is correct