Submission #957881

#TimeUsernameProblemLanguageResultExecution timeMemory
957881vjudge1Abracadabra (CEOI22_abracadabra)C++17
35 / 100
3049 ms25892 KiB
#include<stdio.h> #include<stdlib.h> #define N 200004 int n,a[N],t[N],q,sz[N],at[N],*eh[N],eo[N],zz[1000005]; void upd(int p,int k) { for(;p<N;p|=p+1)t[p]+=k; } int qry(int p) {int z=0;for(;p>0;p&=p-1)z+=t[p-1];return z;} void add(int p,int k) { sz[p]=k; upd(p,k); } void rem(int p) { upd(p,-sz[p]); } int grp(int x) { if(x<=0)return -1; int p=0,v=0; for(int j=1<<19;j>0;j>>=1) if(p+j<=N&&v+t[p+j-1]<x)p+=j,v+=t[p-1]; return p; } void append(int i,int j) { int o=eo[i]++; if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh); eh[i][o]=j; } void shuffle() { int g1=grp(n/2),g2=grp(n/2+1); if(g1!=g2)return; int rl=qry(g1); int st=at[g1]; int md=n/2-rl+at[g1]; int ed=at[g1]+sz[g1]; for(int l=md,j=md;j<=ed;++j) if(j==ed||a[j]>a[l])add(a[l],j-l),l=j; rem(g1); add(g1,n/2-rl); } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;++i)scanf("%d",a+i),at[a[i]]=i; for(int l=1,i=1;i<=n+1;++i) if(i==n+1||a[i]>a[l]) add(a[l],i-l),l=i; for(int i=0;i<=n;++i)eh[i]=(int*)malloc(2*sizeof**eh); for(int t,p,i=0;i<q;++i) { scanf("%d%d",&t,&p); if(t>n)t=n; append(t,i),append(t,p); } for(int i=0;i<=n+1;++i) { for(int j=0;j<eo[i];j+=2) { int gg=grp(eh[i][j+1]); int idx=eh[i][j+1]-qry(gg); zz[eh[i][j]]=a[at[gg]+idx-1]; } shuffle(); } for(int i=0;i<q;++i)printf("%d\n",zz[i]); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void append(int, int)':
Main.cpp:24:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |     if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
      |                 ~^~
Main.cpp: In function 'void shuffle()':
Main.cpp:33:9: warning: unused variable 'st' [-Wunused-variable]
   33 |     int st=at[g1];
      |         ^~
Main.cpp: In function 'int main()':
Main.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:44:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     for(int i=1;i<=n;++i)scanf("%d",a+i),at[a[i]]=i;
      |                          ~~~~~^~~~~~~~~~
Main.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d%d",&t,&p);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...