| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29839 |
2017-07-21T08:19:07 Z |
rondojim |
Cake (CEOI14_cake) |
C++14 |
|
886 ms |
17648 KB |
#include "bits/stdc++.h"
#define MAXN 500009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
#define left cep
#define right sag
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,a,arr[MAXN],p[MAXN],s[MAXN<<2],F[MAXN*2];
void update(int p,int v,int nd,int x,int y){
if(x==y){
s[nd]=v;
return;
}
int mid=(x+y)>>1;
if(p<=mid)
update(p,v,nd<<1,x,mid);
else
update(p,v,nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
int tap(int l,int r,int nd,int x,int y){
if(l>y or x>r)
return INF;
if(l<=x and y<=r)
return s[nd];
int mid=(x+y)>>1;
return min(tap(l,r,nd<<1,x,mid),tap(l,r,nd<<1|1,mid+1,y));
}
int left(int l,int r,int v,int nd,int x,int y){
if(l>y or x>r or s[nd]>v)
return -1;
if(x==y)
return x;
int mid=(x+y)>>1;
int ii=left(l,r,v,nd<<1,x,mid);
if(~ii)
return ii;
return left(l,r,v,nd<<1|1,mid+1,y);
}
int right(int l,int r,int v,int nd,int x,int y){
if(l>y or x>r or s[nd]>v)
return -1;
if(x==y)
return x;
int mid=(x+y)>>1;
int ii=right(l,r,v,nd<<1|1,mid+1,y);
if(~ii)
return ii;
return right(l,r,v,nd<<1,x,mid);
}
void change(int x,int val){
x+=MAXN;
for(;x<MAXN*2;x+=x&(-x))
F[x]+=val;
}
void upd(int p,int x){
change(arr[p],-1);
change(x,+1);
arr[p]=x;
update(p,x,1,1,n);
}
int get(int x){x+=MAXN;
int res=0;
for(;x;x-=x&(-x))
res+=F[x];
return res;
}
int main(){
//~ #ifndef ONLINE_JUDGE
//~ freopen("file.in", "r", stdin);
//~ freopen("file.out", "w", stdout);
//~ #endif
scanf("%d%d",&n,&a);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
p[n-x+1]=i;arr[i]=n-x+1;
change(n-x+1,+1);
update(i,n-x+1,1,1,n);
}
int q;
scanf("%d",&q);
while(q--){
char c;
scanf(" %c",&c);
if(c=='F'){
int x;
scanf("%d",&x);
if(x==a){
puts("0");
continue;
}
if(x<a){
int mx=tap(x,a-1,1,1,n);
int pos=left(a+1,n,mx,1,1,n);
if(pos==-1)
printf("%d\n",n-x);
else
printf("%d\n",pos-x-1);
}
else{
int mx=tap(a+1,x,1,1,n);
int pos=right(1,a-1,mx,1,1,n);
if(pos==-1)
printf("%d\n",x-1);
else
printf("%d\n",x-pos-1);
}
}
else{
int x,y;
scanf("%d%d",&x,&y);
//~ printf("E %d %d\n",x,y);
int rank=get(arr[x]);
//~ debug(rank);
//~ debug(y);
if(rank==y)
continue;
if(y<rank){
int val=arr[p[y]];
upd(x,--val);
for(int i=y-1;i>=1;i--)
upd(p[i],--val);
for(int i=min(10,rank);i>y;i--)
p[i]=p[i-1];
p[y]=x;
}
else{
int val=arr[p[y]];
assert(p[rank]==x);
for(int i=rank;i<y;i++)
p[i]=p[i+1];
p[y]=x;
for(int i=y;i>=rank;i--)
upd(p[i],val--);
}
//~ for(int i=1;i<=n;i++)
//~ cout<<arr[i]<<" ";
//~ cout<<endl;
//~ for(int i=1;i<=n;i++)
//~ cout<<p[i]<<" ";
//~ cout<<endl;
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&a);
^
cake.cpp:90:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
cake.cpp:96:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
cake.cpp:99:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
^
cake.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
cake.cpp:126:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17648 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17648 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17648 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17648 KB |
Output is correct |
| 5 |
Correct |
9 ms |
17648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
449 ms |
17648 KB |
Output is correct |
| 2 |
Correct |
236 ms |
17648 KB |
Output is correct |
| 3 |
Correct |
283 ms |
17648 KB |
Output is correct |
| 4 |
Correct |
166 ms |
17648 KB |
Output is correct |
| 5 |
Correct |
439 ms |
17648 KB |
Output is correct |
| 6 |
Correct |
369 ms |
17648 KB |
Output is correct |
| 7 |
Correct |
366 ms |
17648 KB |
Output is correct |
| 8 |
Correct |
243 ms |
17648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
17648 KB |
Output is correct |
| 2 |
Correct |
113 ms |
17648 KB |
Output is correct |
| 3 |
Correct |
113 ms |
17648 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17648 KB |
Output is correct |
| 5 |
Correct |
216 ms |
17648 KB |
Output is correct |
| 6 |
Correct |
236 ms |
17648 KB |
Output is correct |
| 7 |
Correct |
166 ms |
17648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
17648 KB |
Output is correct |
| 2 |
Correct |
39 ms |
17648 KB |
Output is correct |
| 3 |
Correct |
79 ms |
17648 KB |
Output is correct |
| 4 |
Correct |
106 ms |
17648 KB |
Output is correct |
| 5 |
Correct |
123 ms |
17648 KB |
Output is correct |
| 6 |
Correct |
146 ms |
17648 KB |
Output is correct |
| 7 |
Correct |
159 ms |
17648 KB |
Output is correct |
| 8 |
Correct |
226 ms |
17648 KB |
Output is correct |
| 9 |
Correct |
886 ms |
17648 KB |
Output is correct |
| 10 |
Correct |
446 ms |
17648 KB |
Output is correct |
| 11 |
Correct |
519 ms |
17648 KB |
Output is correct |
| 12 |
Correct |
806 ms |
17648 KB |
Output is correct |
| 13 |
Correct |
549 ms |
17648 KB |
Output is correct |
