Submission #1165760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165760		fryingduc	Election (BOI18_election)	C++20	100 / 100	366 ms	35820 KiB

election

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5e5 + 5;
const int LG = 20;
int n, q;
string s;
int pfx[maxn], res[maxn];
vector<pair<int, int>> que[maxn];

pair<int, int> tree[maxn << 2];
pair<int, int> operator + (const pair<int, int> &a, const pair<int, int> &b) {
  if (b.first == 1e9) return a;
  if (a.first == 1e9) return b;
  return make_pair(min(a.first, a.second + b.first), a.second +  b.second);
}

void update(int pos, int val, int ind = 1, int l = 1, int r = n) {
  if (l == r) {
    tree[ind] = make_pair(val, val);
    return;    
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) update(pos, val, ind << 1, l, mid);
  else update(pos, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

pair<int, int> get(int x, int y, int ind = 1, int l = 1, int r = n) {
  if (l > y || r < x) return make_pair(1e9, 1e9);
  if (x <= l and r <= y) {
    return tree[ind];
  }
  int mid = (l + r) >> 1;
  return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
}

void solve() {
  cin >> n >> s >> q;
  s = ' ' + s;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    que[r].emplace_back(l, i);
  }
  vector<int> vec;
  for (int i = 1; i <= n; ++i) {
    if (s[i] == 'T') {
      vec.push_back(i);
    } else {
      update(i, 1);
      if (!vec.empty()) {
        update(vec.back(), -1);
        vec.pop_back();
      }
    }
    for (auto [v, id] : que[i]) {
      int p = vec.end() - lower_bound(vec.begin(), vec.end(), v);
      res[id] = p - min(0, get(v, i).first);
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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