Submission #134870

#TimeUsernameProblemLanguageResultExecution timeMemory
134870imyujinSushi (JOI16_sushi)C++14
15 / 100
3522 ms79228 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 410005; const int BUCKET = 633; int X[MAXN], S[MAXN], T[MAXN], P[MAXN]; priority_queue<int> d[BUCKET]; priority_queue<int, vector<int>, greater<int> > q[BUCKET]; void updbuc(int k) { for(int i = k * BUCKET; i < (k + 1) * BUCKET; i++) { q[k].push(X[i]); X[i] = q[k].top(); q[k].pop(); } while(!q[k].empty()) q[k].pop(); } int updnai(int s, int e, int x) { for(int i = s; i <= e; i++) if(X[i] > x) swap(X[i], x); return x; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N, Q; cin >> N >> Q; for(int i = 0; i < N; i++) cin >> X[i]; for(int i = 0; i < Q; i++) cin >> S[i] >> T[i] >> P[i]; for(int i = 0; i < BUCKET * BUCKET; i++) d[i / BUCKET].push(X[i]); for(int i = 0; i < Q; i++) { S[i]--; T[i]--; int ks = S[i] / BUCKET, kt = T[i] / BUCKET; updbuc(ks); if(ks == kt && S[i] <= T[i]) cout << updnai(S[i], T[i], P[i]) << "\n"; else { P[i] = updnai(S[i], (ks + 1) * BUCKET - 1, P[i]); for(int j = (ks + 1) % BUCKET; j != kt; j = (j + 1) % BUCKET) { q[j].push(P[i]); d[j].push(P[i]); P[i] = d[j].top(); d[j].pop(); } updbuc(kt); cout << updnai(kt * BUCKET, T[i], P[i]) << "\n"; } //for(int i = 0; i < N; i++) printf("%d ", X[i]); //printf("\n"); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...