Submission #348552

#	Time	Username	Problem	Language	Result	Execution time	Memory
348552		retsiger	Election (BOI18_election)	C++14	100 / 100	624 ms	28180 KiB

election

#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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18