oj.uz

답안 #110702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110702 2019-05-12T06:19:42 Z ckodser 케이크 (CEOI14_cake) C++14
0 / 100
 919 ms 14020 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=15;


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=e;
    ll r=a;
    if(r<l){
	swap(l,r);
    }
    ll ans=find_seg_max(0,n+5,1,l,r+1);
    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,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+1,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:123: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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 255 ms 768 KB Output isn't correct
2 Incorrect 180 ms 768 KB Output isn't correct
3 Correct 186 ms 856 KB Output is correct
4 Correct 172 ms 768 KB Output is correct
5 Incorrect 249 ms 1152 KB Output isn't correct
6 Incorrect 241 ms 1152 KB Output isn't correct
7 Correct 271 ms 1152 KB Output is correct
8 Correct 210 ms 1172 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 3956 KB Output is correct
2 Incorrect 202 ms 3996 KB Output isn't correct
3 Incorrect 186 ms 3960 KB Output isn't correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Correct 343 ms 9564 KB Output is correct
6 Incorrect 240 ms 9692 KB Output isn't correct
7 Incorrect 205 ms 9696 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 640 KB Output isn't correct
2 Incorrect 85 ms 736 KB Output isn't correct
3 Incorrect 132 ms 2168 KB Output isn't correct
4 Incorrect 143 ms 2296 KB Output isn't correct
5 Incorrect 176 ms 888 KB Output isn't correct
6 Incorrect 306 ms 2712 KB Output isn't correct
7 Incorrect 280 ms 1528 KB Output isn't correct
8 Correct 115 ms 3448 KB Output is correct
9 Incorrect 919 ms 13704 KB Output isn't correct
10 Incorrect 651 ms 1848 KB Output isn't correct
11 Incorrect 775 ms 2684 KB Output isn't correct
12 Correct 874 ms 12868 KB Output is correct
13 Incorrect 715 ms 14020 KB Output isn't correct