Submission #1089577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089577		noyancanturk	Election (BOI18_election)	C++17	100 / 100	528 ms	49416 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int lim=5e5+100;

struct{
  int tree[4*lim],sum[4*lim];
  int P,VAL; 
  void update(int l,int r,int node){
    if(l==r){
      tree[node]=sum[node]=VAL;
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child);
    else update(mid+1,r,child|1);
    tree[node]=min(tree[child]+sum[child|1],tree[child|1]);
    sum[node]=sum[child]+sum[child|1];
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(0,lim-1,1);
  }
  int query(int l,int r,int node){
    if(r<=P)return tree[node];
    int mid=l+r>>1,child=node<<1;
    if(P<mid+1)return query(l,mid,child)+sum[child|1];
    int val1=tree[child]+sum[child|1],val2=query(mid+1,r,child|1);
    return min(val1,val2);
  }
  int query(int p){
    P=p;
    return query(0,lim-1,1);
  }
  int sumquery(int l,int r,int node){
    if(P<=l)return sum[node];
    int mid=l+r>>1,child=node<<1;
    if(mid<P)return sumquery(mid+1,r,child|1);
    return sumquery(l,mid,child)+sum[child|1];
  }
  int sumquery(int p){
    P=p;
    return sumquery(0,lim-1,1);
  }
}st;

struct{
  int tree[lim];
  void update(int p,int val){
    p++;
    while(p<lim){
      tree[p]+=val;
      p+=p&-p;
    }
  }
  int query(int p){
    p++;
    int res=0;
    while(p){
      res+=tree[p];
      p-=p&-p;
    }
    return res;
  }
  int query(int l,int r){
    return query(r)-query(l-1);
  }
}fw;

int main(){
  #ifdef Local
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
  #endif
  int n;
  cin>>n;
  string s;
  cin>>s;
  int m;
  cin>>m;
  int l[m],r[m],ans[m];
  vector<int>queries[n];
  for(int i=0;i<m;i++){
    cin>>l[i]>>r[i];
    l[i]--,r[i]--;
    queries[l[i]].pb(i);
  }
  stack<int>inds;
  for(int L=n-1;0<=L;L--){
    if(s[L]=='C'){
      st.update(L,1);
      if(inds.size()){
        st.update(inds.top(),-1);
        fw.update(inds.top(),-1);
        inds.pop();
      }
    }else{
      inds.push(L);
      fw.update(L,1);
    }
    for(int j:queries[L]){
      int R=r[j];
      int val0=fw.query(L,R);
      int val1=st.query(R);
      int val2=st.sumquery(R+1);
      ans[j]=val0-min(0,val1-val2);
    }
  }
  for(int i:ans){
    cout<<i<<"\n";
  }
}

Compilation message (stderr)

election.cpp: In member function 'void<unnamed struct>::update(int, int, int)':
election.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     int mid=l+r>>1,child=node<<1;
      |             ~^~
election.cpp: In member function 'int<unnamed struct>::query(int, int, int)':
election.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int mid=l+r>>1,child=node<<1;
      |             ~^~
election.cpp: In member function 'int<unnamed struct>::sumquery(int, int, int)':
election.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid=l+r>>1,child=node<<1;
      |             ~^~

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