Submission #157761

#TimeUsernameProblemLanguageResultExecution timeMemory
157761TadijaSebezSushi (JOI16_sushi)C++11
100 / 100
9197 ms7056 KiB
#include <bits/stdc++.h> using namespace std; const int N=400050; const int S=777; const int M=N/S+1; const int Q=25050; priority_queue<pair<int,int>> st[M]; int a[N],n,q; bool mark[N]; int Push(int B, int x) { st[B].push({x,0}); int p;tie(x,p)=st[B].top(); st[B].pop(); if(p) mark[-p]=1; return x; } void BuildBlock(int B, int l, int r){ for(int i=l;i<=r;i++) st[B].push({a[i],-i}),mark[i]=0;} void BreakBlock(int B) { int l=B*S,r=min((B+1)*S,n)-1; for(int i=r;i>=l;i--) { if(mark[i]) { int x,y; do { tie(x,y)=st[B].top(); st[B].pop(); }while(-y>i); a[i]=x; if(y) mark[-y]=1; } } while(st[B].size()) st[B].pop(); } int Push(int B, int l, int r, int x) { BreakBlock(B); for(int i=l;i<=r;i++) if(a[i]>x) swap(a[i],x); BuildBlock(B,B*S,min((B+1)*S,n)-1); return x; } void BuildAll(){ for(int l=0;l<n;l+=S) BuildBlock(l/S,l,min(l+S,n)-1);} int Query(int l, int r, int x) { int L=l/S,R=r/S; if(L==R) { x=Push(L,l,r,x); } else { x=Push(L,l,L*S+S-1,x); for(int i=L+1;i<R;i++) x=Push(i,x); x=Push(R,R*S,r,x); } return x; } int main() { scanf("%i %i",&n,&q); for(int i=0;i<n;i++) scanf("%i",&a[i]); BuildAll(); while(q--) { int l,r,x; scanf("%i %i %i",&l,&r,&x); l--;r--; if(l<=r) x=Query(l,r,x); else x=Query(0,r,Query(l,n-1,x)); printf("%i\n",x); } return 0; }

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:64:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%i",&a[i]);
                       ~~~~~^~~~~~~~~~~~
sushi.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&l,&r,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...