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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 400000;
const int MAXQ = 25000;
int N, Q, A[MAXN+10], SQ;
priority_queue<int> PQ1[MAXN+10];
priority_queue<int, vector<int>, greater<int>> PQ2[MAXN+10];
int solve(int S, int T, int P)
{
int i, j;
if(S/SQ==T/SQ)
{
int l=max(1, S/SQ*SQ), r=min(N, S/SQ*SQ+SQ-1);
for(i=l; i<=r; i++)
{
PQ2[S/SQ].push(A[i]);
A[i]=PQ2[S/SQ].top(); PQ2[S/SQ].pop();
}
while(!PQ2[S/SQ].empty()) PQ2[S/SQ].pop();
while(!PQ1[S/SQ].empty()) PQ1[S/SQ].pop();
for(i=S; i<=T; i++) if(P<A[i]) swap(A[i], P);
for(i=l; i<=r; i++) PQ1[S/SQ].push(A[i]);
}
else
{
int l, r;
l=max(1, S/SQ*SQ), r=min(N, S/SQ*SQ+SQ-1);
for(i=l; i<=r; i++)
{
PQ2[S/SQ].push(A[i]);
A[i]=PQ2[S/SQ].top(); PQ2[S/SQ].pop();
}
while(!PQ2[S/SQ].empty()) PQ2[S/SQ].pop();
while(!PQ1[S/SQ].empty()) PQ1[S/SQ].pop();
for(i=S; i<=r; i++) if(P<A[i]) swap(A[i], P);
for(i=l; i<=r; i++) PQ1[S/SQ].push(A[i]);
for(i=S/SQ+1; i<T/SQ; i++)
{
PQ1[i].push(P);
PQ2[i].push(P);
P=PQ1[i].top();
PQ1[i].pop();
}
l=max(1, T/SQ*SQ), r=min(N, T/SQ*SQ+SQ-1);
for(i=l; i<=r; i++)
{
PQ2[T/SQ].push(A[i]);
A[i]=PQ2[T/SQ].top(); PQ2[T/SQ].pop();
}
while(!PQ2[T/SQ].empty()) PQ2[T/SQ].pop();
while(!PQ1[T/SQ].empty()) PQ1[T/SQ].pop();
for(i=l; i<=T; i++) if(P<A[i]) swap(A[i], P);
for(i=l; i<=r; i++) PQ1[T/SQ].push(A[i]);
}
return P;
}
int main()
{
int i, j;
scanf("%d%d", &N, &Q);
SQ=400;
priority_queue<int> PQ;
for(i=1; i<=N; i++)
{
scanf("%d", &A[i]);
PQ1[i/SQ].push(A[i]);
}
while(Q--)
{
int S, T, P;
scanf("%d%d%d", &S, &T, &P);
if(S<=T) printf("%d\n", solve(S, T, P));
else
{
P=solve(S, N, P);
printf("%d\n", solve(1, T, P));
}
/*
for(i=0; i<=N/SQ; i++)
{
printf("bucket : %d\n", i);
vector<int> V;
printf("PQ1 : ");
while(!PQ1[i].empty()) printf("%d ", PQ1[i].top()), V.push_back(PQ1[i].top()), PQ1[i].pop(); printf("\n");
while(!V.empty()) PQ1[i].push(V.back()), V.pop_back();
printf("PQ2 : ");
while(!PQ2[i].empty()) printf("%d ", PQ2[i].top()), V.push_back(PQ2[i].top()), PQ2[i].pop(); printf("\n");
while(!V.empty()) PQ2[i].push(V.back()), V.pop_back();
}
for(i=1; i<=N; i++) printf("%d ", A[i]); printf("\n");
printf("============\n");
*/
}
}
Compilation message (stderr)
sushi.cpp: In function 'int solve(int, int, int)':
sushi.cpp:17:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
sushi.cpp: In function 'int main()':
sushi.cpp:69:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
sushi.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i]);
~~~~~^~~~~~~~~~~~~
sushi.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &S, &T, &P);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |