oj.uz

Submission #110706

# Submission time Handle Problem Language Result Execution time Memory
110706 2019-05-12T06:23:09 Z ckodser Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 2684 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++){
	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 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

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 512 KB Output isn't correct
2 Incorrect 120 ms 692 KB Output isn't correct
3 Correct 129 ms 624 KB Output is correct
4 Correct 117 ms 628 KB Output is correct
5 Incorrect 151 ms 760 KB Output isn't correct
6 Incorrect 165 ms 748 KB Output isn't correct
7 Correct 139 ms 748 KB Output is correct
8 Correct 124 ms 748 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 1676 KB Time limit exceeded
2 Execution timed out 2031 ms 1900 KB Time limit exceeded
3 Execution timed out 2063 ms 1912 KB Time limit exceeded
4 Incorrect 2 ms 384 KB Output isn't correct
5 Execution timed out 2024 ms 2684 KB Time limit exceeded
6 Execution timed out 2029 ms 2684 KB Time limit exceeded
7 Execution timed out 2053 ms 2628 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 808 KB Output isn't correct
2 Incorrect 90 ms 632 KB Output isn't correct
3 Incorrect 669 ms 1332 KB Output isn't correct
4 Incorrect 714 ms 1284 KB Output isn't correct
5 Incorrect 202 ms 1036 KB Output isn't correct
6 Incorrect 1840 ms 1700 KB Output isn't correct
7 Incorrect 500 ms 1176 KB Output isn't correct
8 Correct 110 ms 1280 KB Output is correct
9 Execution timed out 2057 ms 2656 KB Time limit exceeded
10 Incorrect 608 ms 1748 KB Output isn't correct
11 Execution timed out 2065 ms 2064 KB Time limit exceeded
12 Execution timed out 2052 ms 2296 KB Time limit exceeded
13 Execution timed out 2051 ms 2520 KB Time limit exceeded