Submission #134869

#	Time	Username	Problem	Language	Result	Execution time	Memory
134869		imyujin	Sushi (JOI16_sushi)	C++14	0 / 100	1822 ms	42984 KiB

sushi

#include <bits/stdc++.h>
using namespace std;

typedef priority_queue<int, vector<int>, greater<int> > gpq;

const int MAXN = 401005;
const int BUCKET = 633;

int X[MAXN], S[MAXN], T[MAXN], P[MAXN];
priority_queue<int> d[BUCKET];
gpq 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]);
			int j = (ks + 1) % BUCKET;
			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();
				j = (j + 1) % BUCKET;
			}
			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;
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:44:8: warning: unused variable 'j' [-Wunused-variable]
    int j = (ks + 1) % BUCKET;
        ^

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