Submission #654541

#	Time	Username	Problem	Language	Result	Execution time	Memory
654541		Valera_Grinenko	Election (BOI18_election)	C++17	0 / 100	11 ms	16048 KiB

election

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct stmnmx {
  static const int Nmax = 1e6 + 42;
  int Nst;
  int st[Nmax * 4];
  int id = 0;
  #define mnmx min
  void init_(int v, int tl, int tr) {
    if(tl == tr) st[v] = id;
    else {
      int tm = (tl + tr) / 2;
      init_((v << 1), tl, tm);
      init_((v << 1) + 1, tm + 1, tr);
      st[v] = mnmx(st[(v << 1)], st[(v << 1) + 1]);
    }
  }
  void init(int N) {
    Nst = N;
    init_(1, 0, Nst - 1);
  }
  int get_(int l, int r, int v, int tl, int tr) {
    if(l > r) return id;
    if(l == tl && r == tr) return st[v];
    int tm = ((tl + tr) >> 1);
    return mnmx(get_(l, min(r, tm), (v << 1), tl, tm), get_(max(l, tm + 1), r, (v << 1) + 1, tm + 1, tr));
  }
  int get(int l, int r) {
    return get_(l, r, 1, 0, Nst - 1);
  }
  void upd_(int pos, int new_v, int v, int tl, int tr) {
    if(tl == tr) st[v] = new_v;
    else {
      int tm = ((tl + tr) >> 1);
      if(pos <= tm) upd_(pos, new_v, (v << 1), tl, tm);
      else upd_(pos, new_v, (v << 1) + 1, tm + 1, tr);
      st[v] = mnmx(st[(v << 1)], st[(v << 1) + 1]);
    }
  }
  void upd(int pos, int new_v) {
    return upd_(pos, new_v, 1, 0, Nst - 1);
  }
};
struct stsum {
  int Nst;
  vector<ll> st;
  void init_(int v, int tl, int tr) {
    if(tl == tr) st[v] = 0;
    else {
      int tm = (tl + tr) / 2;
      init_((v << 1), tl, tm);
      init_((v << 1) + 1, tm + 1, tr);
      st[v] = 0;
    }
  }
  void init(int n) {
    Nst = n;
    st.resize(4 * n);
    init_(1, 0, Nst - 1);
  }
  ll get_(int l, int r, int v, int tl, int tr) {
    if(l > r) return 0;
    if(l == tl && r == tr) return st[v];
    int tm = ((tl + tr) >> 1);
    return get_(l, min(r, tm), (v << 1), tl, tm) + get_(max(l, tm + 1), r, (v << 1) + 1, tm + 1, tr);
  }
  ll get(int l, int r) {
    return get_(l, r, 1, 0, Nst - 1);
  }
  void set_(int pos, ll value, int v, int tl, int tr) {
    if(tl == tr) st[v] = value;
    else {
      int tm = ((tl + tr) >> 1);
      if(pos <= tm) set_(pos, value, (v << 1), tl, tm);
      else set_(pos, value, (v << 1) + 1, tm + 1, tr);
      st[v] = st[(v << 1)] + st[(v << 1) + 1];
    }
  }
  void set(int pos, ll value) {
    set_(pos, value, 1, 0, Nst - 1);
  }
  void add_(int pos, ll delta, int v, int tl, int tr) {
    if(tl == tr) st[v] += delta;
    else {
      int tm = ((tl + tr) >> 1);
      if(pos <= tm) add_(pos, delta, (v << 1), tl, tm);
      else add_(pos, delta, (v << 1) + 1, tm + 1, tr);
      st[v] = st[(v << 1)] + st[(v << 1) + 1];
    }
  }
  void add(int pos, ll delta) {
    add_(pos, delta, 1, 0, Nst - 1);
  }
  int get_by_order_(int v, int tl, int tr, int k) {
    if(tl == tr) return tl;
    int tm = (tl + tr) / 2;
    if(st[(v << 1)] >= k) return get_by_order_((v << 1), tl, tm, k);
    else return get_by_order_((v << 1) + 1, tm + 1, tr, k - st[(v << 1)]);
  }
  int get_by_order(int k) {
    return get_by_order_(1, 0, Nst - 1, k + 1);
  }
};
void solve() {
  int n, q;
  cin >> n;
  string s; cin >> s;
  cin >> q;
  string rs = s; reverse(all(rs));
  s += rs;
  n *= 2;
  vector<int> pref(n + 1), amT(n + 1);
  vector<int> posT(n + 1, -1);
  stmnmx st; st.init(n + 1);
  for(int i = 0; i < n; i++) {
    amT[i + 1] = amT[i] + (s[i] == 'T');
    if(posT[amT[i + 1]] == -1) posT[amT[i + 1]] = i + 1;
    pref[i + 1] = pref[i] + (s[i] == 'C' ? 1 : -1);
    st.upd(i + 1, pref[i + 1]);
  }
  while(q--) {
    int l, r;
    cin >> l >> r;
    int mn1 = st.get(l, r) - pref[l - 1];
    int take1 = 0, take2 = 0;
    if(mn1 < 0) take1 = -mn1;
    if(take1 == amT[r] - amT[l - 1]) { cout << take1 << '\n'; continue; }
    int pref1 = pref[r] - pref[l - 1] + take1;
    int l2 = -1, r2 = -1;
    if(take1 == 0) {
      l2 = n - r + 1;
      r2 = n - l + 1;
    } else {
      int haveT = amT[l - 1];
      int needT = haveT + take1;
      int pos_needT = posT[needT];
      pos_needT++;
      l2 = n - r + 1;
      r2 = n - pos_needT + 1;
    }
    int mn2 = st.get(l2, r2) - pref[l2 - 1];
    if(mn2 < 0) take2 = -mn2;
    cout << take1 + take2 << '\n';
  }
}
int main() {

  ios::sync_with_stdio(0); cin.tie(0);

  int t = 1;

  // cin >> t;

  while(t--) solve();

  return 0;
}
/*
+++------++ ++------+++
1 2 3 2 1 0 -1 -2 -3 -2 -1 | 0 1 0 -1 -2 -3 -4 -5 -4 -3 -2
1 2 3 2 1 0 -1 -2 -3 -2 -1 | 0 1 0 -1 -2 -3 -4 -5 -4 -3 -2

CCCXXXXTTTCC CCTTTXXXCCC

?
*/

Compilation message (stderr)

election.cpp: In function 'void solve()':
election.cpp:141:9: warning: unused variable 'pref1' [-Wunused-variable]
  141 |     int pref1 = pref[r] - pref[l - 1] + take1;
      |         ^~~~~

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