Submission #134875

#	Time	Username	Problem	Language	Result	Execution time	Memory
134875		imyujin	Sushi (JOI16_sushi)	C++14	100 / 100	6877 ms	79316 KiB

sushi

#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 k, int s, int e, int x) {
	for(int i = s; i <= e; i++) if(X[i] > x) swap(X[i], x);
	while(!d[k].empty()) d[k].pop();
	for(int i = k * BUCKET; i < (k + 1) * BUCKET; i++) d[k].push(X[i]);
	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(ks, S[i], T[i], P[i]) << "\n";
		else {
			P[i] = updnai(ks, 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, kt * BUCKET, T[i], P[i]) << "\n";
		}
		//for(int i = 0; i < N; i++) printf("%d ", X[i]);
		//printf("\n");
	}

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80