oj.uz

Submission #134870

# Submission time Handle Problem Language Result Execution time Memory
134870 2019-07-23T11:01:20 Z imyujin Sushi (JOI16_sushi) C++14
15 / 100
 3522 ms 79228 KB 
#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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 8312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3522 ms 77768 KB Output is correct
2 Correct 3454 ms 78992 KB Output is correct
3 Correct 1788 ms 78648 KB Output is correct
4 Correct 3406 ms 79144 KB Output is correct
5 Correct 2840 ms 79168 KB Output is correct
6 Correct 3470 ms 79024 KB Output is correct
7 Correct 3492 ms 79016 KB Output is correct
8 Correct 3437 ms 79192 KB Output is correct
9 Correct 1773 ms 78584 KB Output is correct
10 Correct 2788 ms 78980 KB Output is correct
11 Correct 1642 ms 78584 KB Output is correct
12 Correct 2804 ms 79052 KB Output is correct
13 Correct 3401 ms 79224 KB Output is correct
14 Correct 3467 ms 79092 KB Output is correct
15 Correct 1791 ms 78584 KB Output is correct
16 Correct 3438 ms 79184 KB Output is correct
17 Correct 2852 ms 79224 KB Output is correct
18 Correct 3471 ms 79068 KB Output is correct
19 Correct 3449 ms 79168 KB Output is correct
20 Correct 3457 ms 79228 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 8312 KB Output isn't correct
2 Halted 0 ms 0 KB -