oj.uz

Submission #774870

# Submission time Handle Problem Language Result Execution time Memory
774870 2023-07-06T04:40:27 Z gun_gan Election (BOI18_election) C++17
0 / 100
 10 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) {
      if(pos.empty() || !k) return l - 1;

      auto cnt = lower_bound(pos.begin(), pos.end(), l) - pos.begin();
      return pos[cnt + k - 1];
} 

int getRight(int r, int k) {
      if(pos.empty() || !k) return r + 1;

      auto cnt = upper_bound(pos.begin(), pos.end(), r) - pos.begin();

      return pos[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 ans = 1e9;

            {
                  int lf = pf[l - 1] - st.query(1, 0, N + 1, l - 1, r); // count dari kiri
                  int rg = sf[r + 1] - tt.query(1, 0, N + 1, getLeft(l, lf) + 1, r + 1); // count dari kanan
                  ans = lf + rg;
            }

            {
                  int rg = sf[r + 1] - tt.query(1, 0, N + 1, l, r + 1);
                  int lf = pf[l - 1] - st.query(1, 0, N + 1, l - 1, getRight(r, rg) - 1);
                  ans = min(ans, lf + rg);
            }            

            cout << ans << '\n';
      }
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 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 10 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 10 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -