oj.uz

Submission #110716

# Submission time Handle Problem Language Result Execution time Memory
110716 2019-05-12T06:41:35 Z ckodser Cake (CEOI14_cake) C++14
0 / 100
 908 ms 8340 KB 
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=3e5+500;
const ll inf=1e9+900;
const ll sq=13;


ll p[maxn];
ll seg[4*maxn];

void bild(ll L,ll R,ll node){
    if(L+1==R){
	seg[node]=p[L];
	return ;
    }
    ll mid=(L+R)/2;
    bild(L,mid,2*node);
    bild(mid,R,2*node+1);
    seg[node]=max(seg[2*node+1],seg[2*node]);
}
ll find_first_high_min(ll L,ll R,ll node,ll l,ll r,ll v){
    if(r<=L || R<=l || seg[node]<=v){
	return inf;
    }
    if(L+1==R){
	return L;
    }
    ll mid=(L+R)/2;
    ll e1=find_first_high_min(L,mid,2*node,l,r,v);
    if(e1!=inf)return e1;
    return find_first_high_min(mid,R,2*node+1,l,r,v);
}
ll find_first_high_max(ll L,ll R,ll node,ll l,ll r,ll v){
    if(r<=L || R<=l || seg[node]<=v){
	return inf;
    }
    if(L+1==R){
	return L;
    }
    ll mid=(L+R)/2;
    ll e1=find_first_high_max(mid,R,2*node+1,l,r,v);
    if(e1!=inf)return e1;
    return find_first_high_max(L,mid,2*node,l,r,v);
}
ll find_seg_max(ll L,ll R,ll node,ll l,ll r){
    if(r<=L || R<=l){
	return 0;
    }
    if(l<=L && R<=r){
	return  seg[node];
    }
    ll mid=(L+R)/2;
    return max(find_seg_max(L,mid,2*node,l,r),find_seg_max(mid,R,2*node+1,l,r));
}
void update_seg(ll L,ll R,ll node,ll x,ll v){
    if(L+1==R){
	seg[node]=v;
	return;
    }
    ll mid=(L+R)/2;
    if(x<mid){
	update_seg(L,mid,2*node,x,v);
    }else{
	update_seg(mid,R,2*node+1,x,v);
    }
    seg[node]=max(seg[2*node+1],seg[2*node]);
}



ll n,a;
vector<pii> best;
ll find_max(ll e){
    ll l,r;
    if(e<a){
	l=e;
	r=a;
    }else{
	l=a+1;
	r=e+1;
    }
    ll ans=find_seg_max(0,n+5,1,l,r);
    for(auto e:best){
	if(l<=e.S && e.S<r){
	    ans=max(ans,e.F);
	}
    }
    return ans;
}
ll find_first_high(ll x,ll f){
    if(f==1){
	ll ans=find_first_high_min(0,n+5,1,a+1,n+5,x);
	for(auto e:best){
	    if(e.F>x && e.S>a){
		ans=min(ans,e.S);
	    }
	}
	return ans;
    }else{
	ll ans=find_first_high_max(0,n+5,1,0,a,x);
	for(auto e:best){
	    if(e.F>x && e.S<a){
		ans=max(ans,e.S);
	    }
	}
	return ans;
    }
}
void fixed(ll x,ll v){
    update_seg(0,n+5,1,x,v);
}
void update(ll pos,ll v){
    p[pos]=best[best.size()-v].F+1;
    bool bod=0;
    for(ll i=best.size()-v+1;i<best.size();i++){
	if(best[i].S!=pos){
	    p[best[i].S]++;
	    best[i].F++;
	}else{
	    bod=1;
	    best[i].F=p[pos];
	}
    }
    if(!bod){
	best.pb(mp(p[pos],pos));
    }
    sort(best.begin(),best.end());
    if(best.size()>sq){
	reverse(best.begin(),best.end());
	pii e=best.back();
	fixed(e.S,e.F);
	best.pop_back();
	reverse(best.begin(),best.end());
    }
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>a;
    p[0]=inf;
    p[n+1]=inf;
    for(ll i=1;i<=n;i++){
	cin>>p[i];
	if(p[i]>=n-sq){
	    best.pb(mp(p[i],i));
	}
    }	
    bild(0,n+5,1);
    sort(best.begin(),best.end());
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
	char c;
	cin>>c;
	if(c=='F'){
	    ll e;
	    cin>>e;
	    ll mi=find_max(e);
	    ll o;
	    if(e==a){
		cout<<0<<endl;
		continue;
	    }	
	    if(e<a){
		o=find_first_high(mi,1);
	    }else{
		o=find_first_high(mi,-1);
	    }
	    cout<<abs(o-e)-1<<endl;
	}else{
	    ll p,v;
	    cin>>p>>v;
	    update(p,v);
	}
    }

}

Compilation message

cake.cpp: In function 'void update(long long int, long long int)':
cake.cpp:126:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=best.size()-v+1;i<best.size();i++){
                              ~^~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 640 KB Output isn't correct
2 Correct 204 ms 640 KB Output is correct
3 Correct 181 ms 640 KB Output is correct
4 Correct 153 ms 640 KB Output is correct
5 Incorrect 234 ms 1024 KB Output isn't correct
6 Correct 223 ms 1024 KB Output is correct
7 Correct 189 ms 1024 KB Output is correct
8 Correct 224 ms 1024 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 3816 KB Output is correct
2 Correct 224 ms 3656 KB Output is correct
3 Correct 192 ms 3704 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Correct 242 ms 7288 KB Output is correct
6 Incorrect 256 ms 7288 KB Output isn't correct
7 Correct 283 ms 6904 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 712 KB Output isn't correct
2 Correct 73 ms 660 KB Output is correct
3 Correct 122 ms 2068 KB Output is correct
4 Correct 121 ms 2012 KB Output is correct
5 Incorrect 189 ms 892 KB Output isn't correct
6 Correct 227 ms 2332 KB Output is correct
7 Correct 265 ms 1272 KB Output is correct
8 Correct 111 ms 3320 KB Output is correct
9 Incorrect 902 ms 8340 KB Output isn't correct
10 Incorrect 553 ms 1528 KB Output isn't correct
11 Correct 705 ms 2480 KB Output is correct
12 Correct 908 ms 7896 KB Output is correct
13 Incorrect 687 ms 8312 KB Output isn't correct