This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N=400050;
const int S=447;
vector<int> pos[N/S];
multiset<int> st[N/S];
int a[N];
int Push(int B, int x)
{
st[B].insert(x);
x=*st[B].rbegin();
st[B].erase(--st[B].end());
return x;
}
void BuildBlock(int B, int l, int r)
{
pos[B].clear();
for(int i=r;i>=l;i--)
{
while(pos[B].size() && a[pos[B].back()]<a[i]) pos[B].pop_back();
pos[B].push_back(i);
}
for(int i:pos[B]) st[B].insert(a[i]);
}
void BreakBlock(int B)
{
while(pos[B].size())
{
a[pos[B].back()]=*st[B].begin();
pos[B].pop_back();
st[B].erase(st[B].begin());
}
}
int n,q;
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:60: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:61: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:66: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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |