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>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef vector<int> vim;
typedef pair<int, int> pii;
const int sz = 500;
int N, M, Q, X[400010];
vector<pii> B[810]; priority_queue<int> S[810];
inline void make(int t) {
B[t].clear(); while(!S[t].empty()) S[t].pop();
int ub=min((t+1)*sz, N);
for (int i=t*sz; i<ub; i++) B[t].eb(X[i], i);
sort(all(B[t])); reverse(all(B[t]));
for (auto &i:B[t]) S[t].em(i.fi);
}
inline void upd(int t) {
for (auto &i:B[t]) { i.fi=S[t].top(); X[i.se]=i.fi; S[t].pop(); }
for (auto &i:B[t]) S[t].em(i.fi);
}
inline int sol(int t, int p) {
S[t].em(p); p=S[t].top(); S[t].pop();
return p;
}
inline int f(int s, int e, int p) {
int st=s/sz, et=e/sz;
upd(st); upd(et);
if (st==et) { for (int i=s; i<=e; i++) if (p<X[i]) swap(p, X[i]); }
else {
for (int i=s; i<min(N, (st+1)*sz); i++) if (p<X[i]) swap(p, X[i]);
for (int i=st+1; i<et; i++) p=sol(i, p);
for (int i=et*sz; i<=e; i++) if (p<X[i]) swap(p, X[i]);
}
make(st); make(et);
return p;
}
int main() {
scanf("%d %d", &N, &Q); M=(N+sz-1)/sz;
for (int i=0; i<N; i++) scanf("%d", &X[i]);
for (int i=0; i<M; i++) make(i);
while (Q--) {
int s, t, p;
scanf("%d %d %d", &s, &t, &p); s--; t--;
if (s>t) printf("%d\n", f(0, t, f(s, N-1, p)));
else printf("%d\n", f(s, t, p));
}
return 0;
}
Compilation message (stderr)
sushi.cpp: In function 'int main()':
sushi.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q); M=(N+sz-1)/sz;
~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:49:31: 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("%d", &X[i]);
~~~~~^~~~~~~~~~~~~
sushi.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &s, &t, &p); s--; t--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |