| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 49150 | 2018-05-22T19:45:16 Z | khohko | Cake (CEOI14_cake) | C++17 | 2000 ms | 41684 KB |
#include <bits/stdc++.h>
//glhf nikabb u suck
#pragma GCC optimize("O3")
using namespace std;
#define ll int
#define lol long long
#define pb push_back
//#define mp make_pair
#define fr first
#define sc second
#define MAX ((lol)(1e9+100))
#define MX ((lol)(4e9+100))
#define ARRS ((lol)(1e6+100))
#define ARS ((lol)(1e3+100))
#define HS ((lol)(233))
#define MOD ((lol)(1e9+9))
#define EP ((double)(1e-9))
#define EPS ((double)(1e-8))
#define pb push_back
#define PI ((double)3.141592653)
#define LG 21
using namespace std;
struct node{
node *L,*R;
ll x;
node(){
L=R=NULL;
x=-MAX;
}
void updt(){
x=-MAX;
if(L)x=max(x,L->x);
if(R)x=max(x,R->x);
}
};
ll wi,wx,wl,wr;
void updt(ll l,ll r,node *& x){
if(wi<l||r-1<wi)return;
if(!x)x=new node();
if(l==r-1){
x->x=wx;
return;
}
updt(l,l+r>>1,x->L);
updt(l+r>>1,r,x->R);
x->updt();
}
ll quer(ll l,ll r,node *& x){
if(wr<l||r-1<wl)return -MAX;
if(!x)return -MAX;
if(wl<=l&&r-1<=wr)return x->x;
return max(quer(l,l+r>>1,x->L),quer(l+r>>1,r,x->R));
}
ll quer1(ll l,ll r,node *& x){
if(wr<l||r-1<wl)return MAX;
if(!x)return MAX;
if(wl<=l&&r-1<=wr){
if(x->x<wx)return MAX;
if(l==r-1)return l;
else if(x->L->x>=wx)
return quer1(l,l+r>>1,x->L);
else return quer1(l+r>>1,r,x->R);
}
return min(quer1(l,l+r>>1,x->L),quer1(l+r>>1,r,x->R));
}
ll quer2(ll l,ll r,node *& x){
if(wr<l||r-1<wl)return -MAX;
if(!x)return -MAX;
if(wl<=l&&r-1<=wr){
if(x->x<wx)return -MAX;
if(l==r-1)return l;
//cout<<l<<" "<<r<<" "<<x->R->x<<" < "<<wx<<endl;
if(x->R->x>=wx)
return quer2(l+r>>1,r,x->R);
else return quer2(l,l+r>>1,x->L);
}
return max(quer2(l,l+r>>1,x->L),quer2(l+r>>1,r,x->R));
}
ll C;
node *rt=NULL;
set<pair<ll,ll> > st;
stack<pair<ll,ll> > sk;
ll n,s;
void add(ll i){
wx=++C;
wi=i;
updt(0,n,rt);
st.insert({wx,i});
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>s;
n+=2;
for(int i=1; i<=n-2; i++){
cin>>wx;
wi=i;
updt(0,n,rt);
st.insert({wx,i});
}
wi=0;
wx=MAX;
updt(0,n,rt);
wi=n-1;
updt(0,n,rt);
ll qr;
char q;
C=n+2;
cin>>qr;
while(qr--){
cin>>q;
if(q=='F'){
ll x;
cin>>x;
if(x==s)
cout<<0<<endl;
else if(x<s){
wl=x;
wr=s-1;
wx=quer(0,n,rt);
wl=s+1;
wr=MAX;
ll t=quer1(0,n,rt);
//cout<<x<<" -> "<<t<<" "<<wx<<" "<<x<<" "<<s-1<<endl;
cout<<t-x-1<<endl;
}
else {
wl=s+1;
wr=x;
wx=quer(0,n,rt);
wl=-MAX;
wr=s-1;
ll t=quer2(0,n,rt);
//cout<<x<<" -> "<<t<<" "<<wx<<" "<<x<<" "<<s-1<<endl;
cout<<x-t-1<<endl;
}
}
else {
ll i,c;
cin>>i>>c;
c--;
while(c--){
sk.push((*--st.end()));
st.erase(--st.end());
}
add(i);
while(sk.size()){
auto k=sk.top();
sk.pop();
add(k.sc);
}
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 248 KB | Output is correct |
| 2 | Incorrect | 3 ms | 484 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1037 ms | 25024 KB | Output isn't correct |
| 2 | Correct | 553 ms | 25224 KB | Output is correct |
| 3 | Correct | 772 ms | 25236 KB | Output is correct |
| 4 | Correct | 392 ms | 25236 KB | Output is correct |
| 5 | Incorrect | 1109 ms | 26768 KB | Output isn't correct |
| 6 | Correct | 936 ms | 26876 KB | Output is correct |
| 7 | Correct | 772 ms | 26876 KB | Output is correct |
| 8 | Correct | 517 ms | 26928 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 404 ms | 26928 KB | Output is correct |
| 2 | Correct | 331 ms | 26928 KB | Output is correct |
| 3 | Correct | 267 ms | 26928 KB | Output is correct |
| 4 | Incorrect | 2 ms | 26928 KB | Output isn't correct |
| 5 | Correct | 623 ms | 28848 KB | Output is correct |
| 6 | Incorrect | 713 ms | 28936 KB | Output isn't correct |
| 7 | Correct | 428 ms | 28936 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 120 ms | 28936 KB | Output isn't correct |
| 2 | Correct | 96 ms | 28936 KB | Output is correct |
| 3 | Correct | 230 ms | 28936 KB | Output is correct |
| 4 | Correct | 282 ms | 28936 KB | Output is correct |
| 5 | Incorrect | 339 ms | 28936 KB | Output isn't correct |
| 6 | Correct | 435 ms | 28936 KB | Output is correct |
| 7 | Correct | 393 ms | 28936 KB | Output is correct |
| 8 | Correct | 517 ms | 28936 KB | Output is correct |
| 9 | Execution timed out | 2037 ms | 40040 KB | Time limit exceeded |
| 10 | Incorrect | 1306 ms | 40040 KB | Output isn't correct |
| 11 | Correct | 1647 ms | 40040 KB | Output is correct |
| 12 | Execution timed out | 2028 ms | 40040 KB | Time limit exceeded |
| 13 | Incorrect | 1605 ms | 41684 KB | Output isn't correct |