oj.uz

Submission #110701

# Submission time Handle Problem Language Result Execution time Memory
110701 2019-05-12T06:18:31 Z ckodser Cake (CEOI14_cake) C++14
0 / 100
 704 ms 6800 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=1e5+500;
const ll inf=1e9+900;
const ll sq=10;


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

# 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 176 ms 5112 KB Output isn't correct
2 Incorrect 230 ms 4472 KB Output isn't correct
3 Correct 215 ms 5060 KB Output is correct
4 Correct 171 ms 3960 KB Output is correct
5 Incorrect 223 ms 4856 KB Output isn't correct
6 Incorrect 257 ms 5372 KB Output isn't correct
7 Correct 271 ms 5372 KB Output is correct
8 Correct 219 ms 4216 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 5124 KB Output is correct
2 Incorrect 237 ms 5240 KB Output isn't correct
3 Incorrect 211 ms 5112 KB Output isn't correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 892 KB Output isn't correct
2 Incorrect 73 ms 1048 KB Output isn't correct
3 Incorrect 119 ms 2808 KB Output isn't correct
4 Incorrect 118 ms 2932 KB Output isn't correct
5 Incorrect 180 ms 1784 KB Output isn't correct
6 Incorrect 231 ms 3964 KB Output isn't correct
7 Incorrect 251 ms 2656 KB Output isn't correct
8 Correct 99 ms 5624 KB Output is correct
9 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 604 ms 4984 KB Output isn't correct
11 Incorrect 704 ms 6800 KB Output isn't correct
12 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)