oj.uz

답안 #440074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440074 2021-07-01T14:45:53 Z leaked Election (BOI18_election) C++14
0 / 100
 17 ms 22092 KB 
#include <bits/stdc++.h>

#define vec vector
#define f first
#define s second
#define endl '\n'
#define pb push_back
#define sz(x) (int)x.size()

using namespace std;
typedef pair<int,int> pii;
const int N=5e5+1;
int lft[N],rgt[N];///for mx
int lwr[N];
int ans[N];
vec<pii>qry[N];
int mn[N][20];
int lvl[N];
int t[4*N],p1[4*N],p2[4*N];
void apply(int v,int x){
    t[v]=x;p1[v]=x;p2[v]=0;
}
void add(int v,int x){
    t[v]+=x;
    if(p1[v]!=2e9){
        p1[v]+=x;
    }
    else{
        p2[v]+=x;
    }
}
void push(int v,int tl,int tr){
    if(tl==tr) return;
    if(p1[v]!=2e9){
        for(auto &u : {2*v,2*v+1}){
            apply(u,p1[v]);
        }
        p1[v]=2e9;
    }
    if(p2[v]){
        for(auto &u : {2*v,2*v+1}){
            add(u,p2[v]);
        }
        p2[v]=0;
    }
}
void upd(int l,int r,int tt,int x,int v,int tl,int tr){
    for(int i=l;i<=r;i++){
        if(tt==0) t[i]=x;
        else t[i]+=x;
    }
}
int get(int id,int v,int tl,int tr){
    return t[id];
}
int getmn(int l,int r){
    int x=lvl[r-l+1];
    return min(mn[l][x],mn[r-(1<<x)+1][x]);
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n;
    vec<int>a(n+1);string s;
    cin>>s;s.insert(s.begin(),'0');
    for(int i=1;i<=n;i++){
        a[i]=(i?a[i-1]:0)+(s[i]=='C'?1:-1);
        mn[i][0]=a[i];
    }
    for(int i=2;i<N;i++) lvl[i]=lvl[i/2]+1;
    for(int j=1;j<20;j++){
        for(int i=0;i+(1<<(j-1))<=n;i++){
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
            //cout<<i<<' '<<j<<' '<<mn[i][j]<<endl;
        }
    }
    vec<pii>vc;
    {
        vc.pb({2e9,-1});
        for(int i=0;i<=n;i++){
            while(sz(vc) && vc.back().f<=a[i]) vc.pop_back();
            lft[i]=vc.back().s;
            vc.pb({a[i],i});
        }
    }
    vc.clear();
    {
        vc.pb({2e9,n+1});
        for(int i=n;i>=0;i--){
            while(sz(vc) && vc.back().f<a[i]) vc.pop_back();
            rgt[i]=vc.back().s;
            vc.pb({a[i],i});
        }
    }
    vc.clear();
    {
        vc.pb({-2e9,-1});
        for(int i=0;i<=n;i++){
            while(sz(vc) && vc.back().f>a[i]) vc.pop_back();
            lwr[i]=vc.back().s;
            vc.pb({a[i],i});
        }
    }
    cin>>q;
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        qry[r].pb({l,i});
    }
    fill(p1,p1+4*N,2e9);
    for(int i=0;i<=n;i++){
        
        ///i need maximum right such that pref[i-1]>pref[r]
       if(i){upd(lft[i-1]+2,i,0,a[i-1],1,0,n);
      //  cout<<"APPLY "<<lft[i-1]+1<<' '<<i<<' '<<a[i-1]<<endl;
       }
        /// i'm in it if l<=i and pref[i]-pref[l-1]<0 lwr[i]>=l(maybe)
        upd(lwr[i]+2,i,1,-1,1,0,n);
       // cout<<"ADD "<<lwr[i]+1<<' '<<i<<' '<<-1<<' '<<a[i]<<endl;

        for(auto &z : qry[i]){
            int l=z.f,r=i;
            int answ=0;
            answ+=max(0,-(getmn(l,r)-a[l-1]));
            //cout<<"MN "<<getmn(l,r)<<' '<<a[l-1]<<endl;
            answ-=min(0,a[r]-get(l,1,0,n)); 

            ans[z.s]=answ;
        }
    }
    for(int i=0;i<q;i++) cout<<ans[i]<<endl;
    return 0;
}

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 22092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 22092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 22092 KB Output isn't correct
2 Halted 0 ms 0 KB -