oj.uz

Submission #348552

# Submission time Handle Problem Language Result Execution time Memory
348552 2021-01-15T07:58:06 Z retsiger Election (BOI18_election) C++14
100 / 100
 624 ms 28180 KB 
#include<bits/stdc++.h>

using namespace std;

const int maxn = 500100;

struct Node {
  int L, R, tot, Ans;

  Node operator + (Node B) {
    Node ret;
    ret.L = max(L, tot + B.L);
    ret.R = max(B.R, R + B.tot);
    ret.tot = tot + B.tot;
    ret.Ans = max({Ans + B.tot, tot + B.Ans, L + B.R});
    return ret;
  }
};

Node T[(maxn << 2)];
string S;
int N;

void build(int v = 1, int l = 1, int r = N) {
  if (l == r) {
    if (S[l] == 'T') T[v] = {1, 1, 1, 1};
    else T[v] = {0, 0, -1, 0};
    return;
  }
  int md = (l + r) >> 1;
  build(v << 1, l, md);
  build(v << 1 | 1, md + 1, r);
  T[v] = T[v << 1] + T[v << 1 | 1];
}

Node get(int v, int l, int r, int x, int y) {
  if (l > y || x > r) return {0, 0, 0, 0};
  if (x <= l && r <= y) return T[v];
  int md = (l + r) >> 1;
  return get(v << 1, l, md, x, y)
        + get(v << 1 | 1, md + 1, r, x, y);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("election.in", "r", stdin);
//  freopen("election.out", "w", stdout);
  cin >> N >> S;
  S = ' ' + S;
  build();
  int Q; cin >> Q;
  while (Q--) {
    int L, R; cin >> L >> R;
    cout << get(1, 1, N, L, R).Ans << '\n';
  }
  return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 60 ms 5884 KB Output is correct
7 Correct 56 ms 5864 KB Output is correct
8 Correct 62 ms 5736 KB Output is correct
9 Correct 55 ms 5736 KB Output is correct
10 Correct 60 ms 5736 KB Output is correct
11 Correct 64 ms 5932 KB Output is correct
12 Correct 61 ms 5892 KB Output is correct
13 Correct 68 ms 5996 KB Output is correct
14 Correct 64 ms 5992 KB Output is correct
15 Correct 64 ms 5872 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 60 ms 5884 KB Output is correct
7 Correct 56 ms 5864 KB Output is correct
8 Correct 62 ms 5736 KB Output is correct
9 Correct 55 ms 5736 KB Output is correct
10 Correct 60 ms 5736 KB Output is correct
11 Correct 64 ms 5932 KB Output is correct
12 Correct 61 ms 5892 KB Output is correct
13 Correct 68 ms 5996 KB Output is correct
14 Correct 64 ms 5992 KB Output is correct
15 Correct 64 ms 5872 KB Output is correct
16 Correct 602 ms 27028 KB Output is correct
17 Correct 515 ms 26568 KB Output is correct
18 Correct 573 ms 26900 KB Output is correct
19 Correct 469 ms 26428 KB Output is correct
20 Correct 604 ms 26132 KB Output is correct
21 Correct 609 ms 27924 KB Output is correct
22 Correct 624 ms 27924 KB Output is correct
23 Correct 620 ms 28180 KB Output is correct
24 Correct 614 ms 27924 KB Output is correct
25 Correct 623 ms 27156 KB Output is correct