Submission #63825

#	Time	Username	Problem	Language	Result	Execution time	Memory
63825		Just_Solve_The_Problem	Election (BOI18_election)	C++11	100 / 100	980 ms	40176 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define pb push_back

const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;

int n;
string s;
vector < pii > query[N];
vector < int > stk;
int b[N];

struct TT {
  int suf, sum;
  TT() {}
};

struct T {
  TT tree[N * 4];
  void upd(int pos, int val, int v = 1, int l = 1, int r = n) {
    if (l == r) {
      tree[v].sum = val;
      tree[v].suf = min(val, 0);
      return ;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
      upd(pos, val, v + v, l, mid);
    } else {
      upd(pos, val, v + v + 1, mid + 1, r);
    }
    tree[v].sum = tree[v + v].sum + tree[v + v + 1].sum;
    tree[v].suf = min(tree[v + v].suf + tree[v + v + 1].sum, tree[v + v + 1].suf);
  }
  pii get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (tl > r || tr < l) return mk(0, 0);
    if (l <= tl && tr <= r) {
      return mk(tree[v].sum, tree[v].suf);
    }
    int mid = (tl + tr) >> 1;
    pii res1, res2;
    res1 = get(l, r, v + v, tl, mid);
    res2 = get(l, r, v + v + 1, mid + 1, tr);
    return mk(res1.fr + res2.fr, min(res1.sc + res2.fr, res2.sc));
  }
};
T tr;

void precalc() {
  for (int i = 1; i <= n; i++) {
    b[i] = ((s[i] == 'C') ? 1 : -1);
    tr.upd(i, 1);
  }
}

int ans[N];

main() {
  scanf("%d", &n);
  cin >> s;
  s = " " + s;
  precalc();
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    query[l].pb(mk(r, i));
  }
  for (int i = n; i >= 1; i--) {
    if (b[i] == -1) {
      stk.pb(i);
      tr.upd(i, 0);
      b[i] = 0;
    } else if (b[i] == 1) {
      if (!stk.empty()) {
        tr.upd(stk.back(), -1);
        b[stk.back()] = -1;
        stk.pop_back();
      }
    }
    for (pii to : query[i]) {
//      cout << upper_bound(stk.rbegin(), stk.rend(), to.fr) - stk.rbegin() << ' ' << tr.get(1, to.fr).sc << endl;
      ans[to.sc] = upper_bound(stk.rbegin(), stk.rend(), to.fr) - stk.rbegin() - tr.get(1, to.fr).sc;
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }
}

Compilation message (stderr)

election.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
election.cpp: In function 'int main()':
election.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
election.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
election.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &l, &r);
     ~~~~~^~~~~~~~~~~~~~~~~

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