oj.uz

Submission #110704

# Submission time Handle Problem Language Result Execution time Memory
110704 2019-05-12T06:22:09 Z ckodser Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 2964 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=5;


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++){
	ans=max(ans,p[i]);
    }
    return ans;
}
ll find_first_high(ll x,ll f){
    for(ll i=a;;i+=f){
	if(p[i]>x)return i;
    }
    return 0;
}
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());
	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));
	}
    }	
    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:44: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 3 ms 384 KB Output is correct
2 Incorrect 2 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 101 ms 384 KB Output isn't correct
2 Incorrect 93 ms 384 KB Output isn't correct
3 Correct 96 ms 384 KB Output is correct
4 Correct 90 ms 384 KB Output is correct
5 Incorrect 103 ms 512 KB Output isn't correct
6 Incorrect 115 ms 512 KB Output isn't correct
7 Correct 106 ms 512 KB Output is correct
8 Correct 115 ms 512 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 1640 KB Time limit exceeded
2 Execution timed out 2028 ms 1556 KB Time limit exceeded
3 Execution timed out 2055 ms 1784 KB Time limit exceeded
4 Incorrect 3 ms 384 KB Output isn't correct
5 Execution timed out 2051 ms 2692 KB Time limit exceeded
6 Execution timed out 2050 ms 2684 KB Time limit exceeded
7 Execution timed out 2063 ms 2808 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 504 KB Output isn't correct
2 Incorrect 89 ms 536 KB Output isn't correct
3 Incorrect 734 ms 1044 KB Output isn't correct
4 Incorrect 767 ms 1084 KB Output isn't correct
5 Incorrect 209 ms 760 KB Output isn't correct
6 Incorrect 1917 ms 1524 KB Output isn't correct
7 Incorrect 610 ms 1080 KB Output isn't correct
8 Correct 111 ms 1280 KB Output is correct
9 Execution timed out 2049 ms 2808 KB Time limit exceeded
10 Incorrect 625 ms 1584 KB Output isn't correct
11 Execution timed out 2050 ms 1948 KB Time limit exceeded
12 Execution timed out 2048 ms 2208 KB Time limit exceeded
13 Execution timed out 2096 ms 2964 KB Time limit exceeded