Submission #630088

#	Time	Username	Problem	Language	Result	Execution time	Memory
630088		czhang2718	Election (BOI18_election)	C++17	0 / 100	2 ms	1492 KiB

election

#include "bits/stdc++.h"
using namespace std;

const int K=19;
int n, q;

// get INDEX of min in [l,r]
struct st{
  vector<int> a;
  vector<vector<int>> mn, mx, nxt, h;

  st(vector<int> a){
    this->a=a;
    mn.resize(K, vector<int>(n+1));
    mx.resize(K, vector<int>(n+1));
    nxt.resize(K, vector<int>(n+1));
    h.resize(K, vector<int>(n+1));
    for(int i=1; i<=n; i++){
      mn[0][i]=mx[0][i]=a[i];
    }
    for(int j=1; j<K; j++){
      for(int i=0; i+(1<<j)<=n+1; i++){
        mn[j][i]=min(mn[j-1][i], mn[j-1][i+(1<<(j-1))]);
      }
    }
    for(int j=1; j<K; j++){
      for(int i=0; i+(1<<j)<=n+1; i++){
        mx[j][i]=max(mx[j-1][i], mx[j-1][i+(1<<(j-1))]);
      }
    }
    for(int i=0; i<=n+1; i++){
      int j=i;
      int _max=a[i];
      for(int k=K-1; k>=0; k--){
        if(j+(1<<k)<=n+1 && mn[k][j]==a[i]){
          _max=max(_max, mx[k][j]);
          j+=(1<<k);
        }
      }
      nxt[0][i]=j;
      h[0][i]=_max-a[i];
      // cout << "nxt " << i <<" " << j << " " << _max << "-" <<a[i] << "\n";
    }
    for(int k=1; k<K; k++){
      for(int i=0; i+(1<<k)<=n+1; i++){
        nxt[k][i]=nxt[k-1][nxt[k-1][i]];
        h[k][i]=max(h[k-1][i], h[k-1][i+(1<<(k-1))]);
      }
    }
  }

  pair<int,int> qry(int l, int r){
    int v=1e9;
    int i=l;
    for(int k=0; k<K; k++){
      if((r-l+1)&(1<<k)){
        v=min(v, mn[k][i]);
        i+=(1<<k);
      }
    }
    // cout << "mn " << l << " " << r << " " << v << "\n";
    i=l;
    for(int k=K-1; k>=0; k--){
      if(i+(1<<k)>r+1) continue;
      if(mn[k][i]>v) i+=(1<<k);
    }
    int ind=l;
    int maxh=-1e9;
    for(int p=K-1; p>=0; p--){
      if(nxt[p][ind] && nxt[p][ind]<=i){
        maxh=max(maxh, h[p][ind]);
        ind=nxt[p][ind];
      }
    }
    return {i, maxh};
  }
};

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  vector<int> a(n+1), b(n+1);
  for(int i=1; i<=n; i++){
    char c; cin >> c;
    a[i]=(c=='C'?1:-1);
  }
  for(int i=n; i>=1; i--){
    b[i]=a[n+1-i];
  }
  for(int i=1; i<=n; i++){
    a[i]+=a[i-1];
    b[i]+=b[i-1];
  }

  st st1(a), st2(b);

  cin >> q;
  while(q--){
    int l,r;
    cin >> l >> r;
    pair<int,int> ii=st1.qry(l-1,r);
    int i=ii.first, mx=ii.second;
    int j=n-st2.qry(n-r, n+1-l).first;
    // cout << "ij " << i << " " << j << "\n";
    // cout << mx << "-" << (a[r]-a[i]) << "\n";
    cout << a[l-1]-a[i]+max(mx-(a[r]-a[i]), a[n-st2.qry(n-r, n-i).first]-a[r]) << '\n';
  }
}
// we're just a room full of strangers

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:104:9: warning: unused variable 'j' [-Wunused-variable]
  104 |     int j=n-st2.qry(n-r, n+1-l).first;
      |         ^

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