Submission #774850

#	Time	Username	Problem	Language	Result	Execution time	Memory
774850		gun_gan	Election (BOI18_election)	C++17	0 / 100	9 ms	15956 KiB

election

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 

const int MX = 5e5 + 5;

int N, Q;
string s;

struct segtree {
      int t[4 * MX];

      void update(int v, int l, int r, int pos, int val) {
            if(r < pos || l > pos) return;
            if(l == r) {
                  t[v] = val;
                  return;
            }

            int mid = (l + r) >> 1;
            update(v * 2 + 0, l, mid + 0, pos, val);
            update(v * 2 + 1, mid + 1, r, pos, val);

            t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
      }

      int query(int v, int l, int r, int ql, int qr) {
            if(l > qr || r < ql) return 1e9;
            if(ql <= l && qr >= r) return t[v];
            int mid = (l + r) >> 1;

            return min(query(v * 2 + 0, l, mid + 0, ql, qr), 
                  query(v * 2 + 1, mid + 1, r, ql, qr));
      }

} st, tt;

int sf[MX], pf[MX];

vector<int> pos;

int getLeft(int l, int k) {
      auto cnt = lower_bound(pos.begin(), pos.end(), l - 1) - pos.begin();
      return cnt + k;
} 

int getRight(int r, int k) {
      auto cnt = upper_bound(pos.begin(), pos.end(), r) - pos.begin();
      return cnt - k;
}

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

      cin >> N >> s >> Q;

      s = '#' + s;

      for(int i = 0; i < 4 * MX; i++) {
            st.t[i] = tt.t[i] = 1e9;
      }
 
      st.update(1, 0, N + 1, 0, 0);
      tt.update(1, 0, N + 1, 0, 0);
      st.update(1, 0, N + 1, N + 1, 0);
      tt.update(1, 0, N + 1, N + 1, 0);

      for(int i = 1; i <= N; i++) {
            pf[i] += (s[i] == 'C' ? 1 : -1) + pf[i - 1];
            st.update(1, 0, N + 1, i, pf[i]);
      }

      for(int i = N; i >= 1; i--) {
            sf[i] += (s[i] == 'C' ? 1 : -1) + sf[i + 1];
            tt.update(1, 0, N + 1, i, sf[i]);
      }

      for(int i = 1; i <= N; i++) {
            if(s[i] == 'T') pos.push_back(i);
      }

      while(Q--) {
            int l, r;
            cin >> l >> r;

            int lf = pf[l - 1] - st.query(1, 0, N + 1, l - 1, r); // count dari kiri
            int x = getLeft(l, lf) - 1;

            int rg = sf[r + 1] - tt.query(1, 0, N + 1, pos[x] + 1, r + 1); // count dari kanan

            cout << lf + rg << '\n';
      }
}

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