Submission #26347

#TimeUsernameProblemLanguageResultExecution timeMemory
26347KerimCake (CEOI14_cake)C++14
100 / 100
863 ms17648 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...