oj.uz

Submission #905018

# Submission time Handle Problem Language Result Execution time Memory
905018 2024-01-12T13:00:23 Z gun_gan Election (BOI18_election) C++17
100 / 100
 936 ms 47096 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 8 ms 15452 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 6 ms 15196 KB Output is correct
5 Correct 6 ms 15196 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 8 ms 15452 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 6 ms 15196 KB Output is correct
5 Correct 6 ms 15196 KB Output is correct
6 Correct 85 ms 21776 KB Output is correct
7 Correct 77 ms 21304 KB Output is correct
8 Correct 86 ms 21384 KB Output is correct
9 Correct 79 ms 21632 KB Output is correct
10 Correct 82 ms 21568 KB Output is correct
11 Correct 99 ms 21844 KB Output is correct
12 Correct 96 ms 21964 KB Output is correct
13 Correct 92 ms 21844 KB Output is correct
14 Correct 90 ms 21704 KB Output is correct
15 Correct 80 ms 21588 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 8 ms 15452 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 6 ms 15196 KB Output is correct
5 Correct 6 ms 15196 KB Output is correct
6 Correct 85 ms 21776 KB Output is correct
7 Correct 77 ms 21304 KB Output is correct
8 Correct 86 ms 21384 KB Output is correct
9 Correct 79 ms 21632 KB Output is correct
10 Correct 82 ms 21568 KB Output is correct
11 Correct 99 ms 21844 KB Output is correct
12 Correct 96 ms 21964 KB Output is correct
13 Correct 92 ms 21844 KB Output is correct
14 Correct 90 ms 21704 KB Output is correct
15 Correct 80 ms 21588 KB Output is correct
16 Correct 823 ms 45436 KB Output is correct
17 Correct 619 ms 42536 KB Output is correct
18 Correct 742 ms 43744 KB Output is correct
19 Correct 755 ms 45108 KB Output is correct
20 Correct 775 ms 44380 KB Output is correct
21 Correct 787 ms 47096 KB Output is correct
22 Correct 864 ms 45720 KB Output is correct
23 Correct 904 ms 46684 KB Output is correct
24 Correct 936 ms 46008 KB Output is correct
25 Correct 800 ms 44724 KB Output is correct