Submission #905018

#	Time	Username	Problem	Language	Result	Execution time	Memory
905018		gun_gan	Election (BOI18_election)	C++17	100 / 100	936 ms	47096 KiB

election

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

const int MX = 5e5 + 5;

int N, Q;
string s;

vector<pair<int,int>> query[MX];
int ans[MX];

struct segtree {
      int t[4 * MX], lazy[4 * MX];
      void push(int v, int l, int r) {
            t[v] += lazy[v];
            if(l != r) {
                  lazy[v * 2 + 0] += lazy[v];
                  lazy[v * 2 + 1] += lazy[v];
            }
            lazy[v] = 0;
      }
      void update(int v, int l, int r, int ql, int qr, int val) {
            push(v, l, r);
            if(l > qr || r < ql) return;
            if(ql <= l && qr >= r) {
                  lazy[v] += val;
                  push(v, l, r);
                  return;
            }
            int mid = (l + r) >> 1;
            update(v * 2 + 0, l, mid + 0, ql, qr, val);
            update(v * 2 + 1, mid + 1, r, ql, qr, val);
            t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
      }
      int query(int v, int l, int r, int ql, int qr) {
            push(v, l, r);
            if(l > qr || r < ql) return -1e9;
            if(ql <= l && qr >= r) return t[v];
            int mid = (l + r) >> 1;
            return max(query(v * 2 + 0, l, mid + 0, ql, qr), 
                  query(v * 2 + 1, mid + 1, r, ql, qr));
      }
} st; // maintain suffix sum

struct fenwick {
      int t[MX];
      void upd(int v, int x) {
            for(int i = v; i <= N; i += i & -i) t[i] += x;
      }
      int que(int x) {
            int res = 0;
            for(int i = x; i > 0; i -= i & -i) res += t[i];
            return res;
      } 
      int que(int x, int y) {
            return que(y) - que(x - 1);
      }
} ds;

/* 
      2 segtree, 1 maintain prefix sum butuh lazy dan range max
      1 lagi BIT buat suffix nya sampe range (l, r) itu berapa yg diapus
*/

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

      cin >> N >> s >> Q;
      for(int i = 0; i < Q; i++) {
            int l, r;
            cin >> l >> r;
            query[r].push_back({l, i});
      }

      vector<int> v;
      for(int i = 1; i <= N; i++) {
            int val = (s[i - 1] == 'C' ? -1 : 1);
            st.update(1, 0, N, i, N, val);
            if(val == 1) {
                  v.push_back(i);
                  ds.upd(i, 1);
                  st.update(1, 0, N, i, N, -1); // di apus di sini
            } else { 
                  if(v.size()) {
                        st.update(1, 0, N, v.back(), N, 1); // balikin lagi itu
                        ds.upd(v.back(), -1);
                        v.pop_back();
                  }
            }
            for(auto [j, id] : query[i]) {
                  ans[id] = max(0, st.query(1, 0, N, j, i) - st.query(1, 0, N, j - 1, j - 1)) + ds.que(j, i);
            }
      }

      for(int i = 0; i < Q; i++) {
            cout << ans[i] << '\n';
      }
}

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