| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26342 |
2017-06-29T08:58:38 Z |
Kerim |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
29324 KB |
#include "bits/stdc++.h"
#include<ext/pb_ds/assoc_container.hpp>
#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;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> PII;
typedef tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> tes;
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];
tes st;
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 upd(int p,int x){
st.erase(mp(arr[p],p));
arr[p]=x;update(p,x,1,1,n);
st.insert(mp(x,p));
}
int main(){
//~ #ifndef ONLINE_JUDGE
//~ freopen("file.in", "r", stdin);
//~ freopen("file.out", "w", stdout);
//~ #endif
scanf("%d%d",&n,&a);
//~ int l=min(10,n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
p[n-x+1]=i;arr[i]=n-x+1;
st.insert(mp(n-x+1,i));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=st.order_of_key(mp(arr[x],-1))+1;
//~ 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=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:79: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:83:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
cake.cpp:88:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
cake.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
^
cake.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
cake.cpp:118: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 |
13748 KB |
Output is correct |
| 2 |
Correct |
0 ms |
13748 KB |
Output is correct |
| 3 |
Correct |
0 ms |
13748 KB |
Output is correct |
| 4 |
Correct |
9 ms |
13880 KB |
Output is correct |
| 5 |
Correct |
49 ms |
14408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1889 ms |
14276 KB |
Output is correct |
| 2 |
Correct |
739 ms |
14408 KB |
Output is correct |
| 3 |
Correct |
1116 ms |
14408 KB |
Output is correct |
| 4 |
Correct |
606 ms |
14408 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
15332 KB |
Execution timed out |
| 6 |
Correct |
1976 ms |
15332 KB |
Output is correct |
| 7 |
Correct |
1803 ms |
15332 KB |
Output is correct |
| 8 |
Correct |
789 ms |
15332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
19952 KB |
Output is correct |
| 2 |
Correct |
176 ms |
19952 KB |
Output is correct |
| 3 |
Correct |
193 ms |
19952 KB |
Output is correct |
| 4 |
Correct |
0 ms |
13748 KB |
Output is correct |
| 5 |
Correct |
496 ms |
29324 KB |
Output is correct |
| 6 |
Correct |
469 ms |
29324 KB |
Output is correct |
| 7 |
Correct |
353 ms |
29324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
14012 KB |
Output is correct |
| 2 |
Correct |
146 ms |
14012 KB |
Output is correct |
| 3 |
Correct |
1216 ms |
16916 KB |
Output is correct |
| 4 |
Correct |
1246 ms |
16916 KB |
Output is correct |
| 5 |
Correct |
356 ms |
13880 KB |
Output is correct |
| 6 |
Execution timed out |
2000 ms |
17840 KB |
Execution timed out |
| 7 |
Correct |
826 ms |
14408 KB |
Output is correct |
| 8 |
Execution timed out |
2000 ms |
19952 KB |
Execution timed out |
| 9 |
Execution timed out |
2000 ms |
29324 KB |
Execution timed out |
| 10 |
Correct |
1129 ms |
13880 KB |
Output is correct |
| 11 |
Execution timed out |
2000 ms |
15068 KB |
Execution timed out |
| 12 |
Execution timed out |
2000 ms |
0 KB |
Execution timed out |
| 13 |
Execution timed out |
2000 ms |
29324 KB |
Execution timed out |
