oj.uz

Submission #110743

# Submission time Handle Problem Language Result Execution time Memory
110743 2019-05-12T07:26:11 Z ckodser Cake (CEOI14_cake) C++14
46.6667 / 100
 2000 ms 2844 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 n,a;
vector<pii> best;

ll find_max(ll e){
    ll l=e;
    ll r=a;
    if(r<l){
	swap(l,r);
    }
    ll ans=0;
    for(ll i=l;i<=r;i++){
	if(i!=a){
	    ans=max(ans,p[i]);
	}
    }
    return ans;
}
ll find_first_high(ll x,ll f){
    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());
	best.pop_back();
	reverse(best.begin(),best.end());
    }  
}
int main(){
    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));
	}
    }	
    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:47: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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 32 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 384 KB Output is correct
2 Correct 364 ms 384 KB Output is correct
3 Correct 319 ms 384 KB Output is correct
4 Correct 329 ms 384 KB Output is correct
5 Correct 349 ms 512 KB Output is correct
6 Correct 350 ms 484 KB Output is correct
7 Correct 330 ms 512 KB Output is correct
8 Correct 393 ms 512 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 1724 KB Time limit exceeded
2 Execution timed out 2048 ms 1676 KB Time limit exceeded
3 Correct 1749 ms 1780 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Execution timed out 2047 ms 2772 KB Time limit exceeded
6 Execution timed out 2019 ms 2776 KB Time limit exceeded
7 Execution timed out 2055 ms 2844 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 536 KB Output is correct
2 Correct 115 ms 632 KB Output is correct
3 Correct 829 ms 1028 KB Output is correct
4 Correct 810 ms 1156 KB Output is correct
5 Correct 247 ms 760 KB Output is correct
6 Execution timed out 2012 ms 1396 KB Time limit exceeded
7 Correct 567 ms 888 KB Output is correct
8 Correct 249 ms 1144 KB Output is correct
9 Execution timed out 2052 ms 2680 KB Time limit exceeded
10 Correct 830 ms 1516 KB Output is correct
11 Execution timed out 2048 ms 1884 KB Time limit exceeded
12 Execution timed out 2048 ms 2292 KB Time limit exceeded
13 Execution timed out 2058 ms 2552 KB Time limit exceeded