Submission #359677

#	Time	Username	Problem	Language	Result	Execution time	Memory
359677		vkgainz	Election (BOI18_election)	C++17	0 / 100	22 ms	31596 KiB

election

#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);
  ret.mx = max(a.mx, b.mx);
  ret.ans = max({a.ans, b.ans-a.sum, b.mx + a.sum - a.mn - ret.sum});
  return ret;
}
int sz = 1;
void build(string &s, int x=0, int lx=0, int rx=sz) {
  if(rx-lx==1) {
    if(lx<s.size()) {
      if(s[lx]=='C') seg[x] = node(1, -1, 1, 1);
      else seg[x] = node(-1, 1, -1, -1);
    }
    else seg[x] = node();
    return;
  }
  int m = (lx+rx)/2;
  build(s, 2*x+1, lx, m), build(s, 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);
  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";
  }
}

Compilation message (stderr)

election.cpp: In function 'void build(std::string&, int, int, int)':
election.cpp:25:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if(lx<s.size()) {
      |        ~~^~~~~~~~~

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