oj.uz

Submission #630536

# Submission time Handle Problem Language Result Execution time Memory
630536 2022-08-16T13:25:02 Z czhang2718 Election (BOI18_election) C++17
0 / 100
 2 ms 1236 KB 
#include "bits/stdc++.h"
using namespace std;

const int N=5e5+1, K=19;
int n, q;
int a[N];
int mn[K][N], mx[K][N], nxt[K][N], h[K][N];

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

  cin >> n;
  vector<int> a(n+1);
  for(int i=1; i<=n; i++){
    char c; cin >> c;
    a[i]=(c=='C'?1:-1)+a[i-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";
  }
  nxt[0][n+1]=n+1;
  h[0][n+1]=-1e9;
  for(int k=1; k<K; k++){
    for(int i=0; i<=n; i++){
      nxt[k][i]=nxt[k-1][nxt[k-1][i]];
      h[k][i]=max(h[k-1][i], h[k-1][nxt[k-1][i]]);
    }
  }

  cin >> q;
  while(q--){
    int l,r;
    cin >> l >> r;

    int minv=1e9;
    int i=l-1;
    for(int k=K-1; k>=0; k--){
      if(i+(1<<k)<=r+1){
        minv=min(minv, mn[k][i]);
        i+=(1<<k);
      }
    }

    int ind=l-1;
    int maxh=-1e9;
    for(int p=K-1; p>=0; p--){
      if(nxt[p][ind] && nxt[p][ind]<=r){
        maxh=max(maxh, h[p][ind]);
        ind=nxt[p][ind];
      }
    }

    // max [lst, r]
    i=ind;
    int maxv=-1e9;
    for(int k=K-1; k>=0; k--){
      if(i+(1<<k)<=r+1){
        maxv=max(maxv, mx[k][i]);
        i+=(1<<k);
      }
    }

    int peak=max(maxh, maxv-minv)+a[l-1];

    // cout << minv << " " << maxv << " " << maxh << " " << peak << "\n";
    cout << a[l-1]-minv + peak-(a[r]+a[l-1]-minv) << "\n";
  }
}
// we're just a room full of strangers

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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