oj.uz

답안 #110752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110752 2019-05-12T07:37:56 Z ckodser 케이크 (CEOI14_cake) C++14
100 / 100
 1416 ms 8312 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=5e5+500;
const ll inf=1e9+900;
const ll sq=12;

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

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=e;
    ll r=a;
    if(r<l){
	swap(l,r);
    }
    if(l==a)l++;
    if(r==a)r--;

    return find_seg_max(0,nmx,1,l,r+1);
    /*
    ll ans=0;
    for(ll i=l;i<=r;i++){
	ans=max(ans,p[i]);
    }
    return ans;*/
}
ll find_first_high(ll x,ll f){
    if(f==1){
	return find_first_high_min(0,nmx,1,a+1,nmx,x);
    }else{
	return find_first_high_max(0,nmx,1,0,a,x);
    }/*
    for(ll i=a+f;;i+=f){
	if(p[i]>x)return i;
    }
    return 0;*/
}
void update(ll x,ll v){
    ll b=best[best.size()-v].F;
    p[x]=b+1;
    bool bod=0;
    for(ll i=0;i<best.size();i++){
	if(best[i].F>b && best[i].S!=x){
	    best[i].F++;
	    p[best[i].S]++;
	}
	if(best[i].S==x){
	    best[i].F=b+1;
	    bod=1;
	}
    }
    if(!bod){
	best.pb(mp(p[x],x));
    }
    sort(best.begin(),best.end());
    if(best.size()>sq){
	reverse(best.begin(),best.end());
	pii e=best.back();
	update_seg(0,nmx,1,e.S,e.F);
	best.pop_back();
	reverse(best.begin(),best.end());
    }  
    for(auto e:best){
	update_seg(0,nmx,1,e.S,e.F);
    }
}
int main(){
    cin>>n>>a;
    nmx=n+5;
    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,nmx,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 x,v;
	    cin>>x>>v;
	    update(x,v);
	}
    }

}

Compilation message

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 11 ms 384 KB Output is correct
5 Correct 29 ms 760 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 859 ms 640 KB Output is correct
2 Correct 738 ms 640 KB Output is correct
3 Correct 680 ms 640 KB Output is correct
4 Correct 640 ms 640 KB Output is correct
5 Correct 898 ms 1024 KB Output is correct
6 Correct 803 ms 1152 KB Output is correct
7 Correct 898 ms 1024 KB Output is correct
8 Correct 825 ms 1024 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 3788 KB Output is correct
2 Correct 283 ms 3576 KB Output is correct
3 Correct 240 ms 3524 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 326 ms 7160 KB Output is correct
6 Correct 311 ms 7180 KB Output is correct
7 Correct 357 ms 6904 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 504 KB Output is correct
2 Correct 109 ms 632 KB Output is correct
3 Correct 197 ms 2040 KB Output is correct
4 Correct 195 ms 1916 KB Output is correct
5 Correct 294 ms 804 KB Output is correct
6 Correct 415 ms 2368 KB Output is correct
7 Correct 441 ms 1212 KB Output is correct
8 Correct 497 ms 3292 KB Output is correct
9 Correct 1370 ms 8244 KB Output is correct
10 Correct 918 ms 1696 KB Output is correct
11 Correct 1205 ms 2492 KB Output is correct
12 Correct 1416 ms 7616 KB Output is correct
13 Correct 1123 ms 8312 KB Output is correct