oj.uz

Submission #774850

# Submission time Handle Problem Language Result Execution time Memory
774850 2023-07-06T04:17:31 Z gun_gan Election (BOI18_election) C++17
0 / 100
 9 ms 15956 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -