oj.uz

답안 #110734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110734 2019-05-12T07:08:28 Z ckodser 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 2824 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=1e15+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 anss=0;
    for(ll i=l;i<r;i++){
	anss=max(anss,p[i]);
    }
    return anss;
/*




    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){
    for(ll i=a+f;;i+=f){
	if(p[i]>x)return i;
    }
    exit(1);

/*

    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){
    ll b=n-v+1;
    ll a=p[pos];

    for(ll i=1;i<=n;i++){
	if(p[i]==a){
	    p[i]=b;
	}
	else if(b<=p[i]){
	    p[i]++;
	}
    }

    /*
    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);
	}
    }

}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2017 ms 384 KB Time limit exceeded
2 Execution timed out 2025 ms 384 KB Time limit exceeded
3 Execution timed out 2051 ms 384 KB Time limit exceeded
4 Execution timed out 2044 ms 384 KB Time limit exceeded
5 Execution timed out 2051 ms 632 KB Time limit exceeded
6 Execution timed out 2039 ms 512 KB Time limit exceeded
7 Execution timed out 2045 ms 512 KB Time limit exceeded
8 Execution timed out 2053 ms 512 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2041 ms 1592 KB Time limit exceeded
2 Incorrect 1921 ms 1792 KB Output isn't correct
3 Incorrect 858 ms 1656 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Execution timed out 2041 ms 2680 KB Time limit exceeded
6 Execution timed out 2037 ms 2536 KB Time limit exceeded
7 Execution timed out 2047 ms 2824 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 436 KB Output isn't correct
2 Incorrect 315 ms 632 KB Output isn't correct
3 Execution timed out 2033 ms 1024 KB Time limit exceeded
4 Execution timed out 2032 ms 1148 KB Time limit exceeded
5 Incorrect 341 ms 760 KB Output isn't correct
6 Execution timed out 2066 ms 1144 KB Time limit exceeded
7 Incorrect 1919 ms 1108 KB Output isn't correct
8 Execution timed out 2063 ms 1152 KB Time limit exceeded
9 Execution timed out 2058 ms 2552 KB Time limit exceeded
10 Incorrect 1026 ms 1804 KB Output isn't correct
11 Execution timed out 2037 ms 948 KB Time limit exceeded
12 Execution timed out 2059 ms 2040 KB Time limit exceeded
13 Execution timed out 2052 ms 2636 KB Time limit exceeded