Submission #202635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
202635	2020-02-17T12:00:32 Z	maruii	Sushi (JOI16_sushi)	C++14	15 / 100	3199 ms	86264 KB

sushi

#include <bits/stdc++.h>
using namespace std;
const int B = 600;

int A[400005];
priority_queue<int> q[700];
vector<int> stk[700];
int naive(int s, int e, int v) {
	if (s > e) return v;
	int a = (s - 1) / B;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (auto i : stk[a]) pq.push(i);
	stk[a].clear();
	for (int i = a * B + 1; i <= a * B + B; ++i) {
		pq.push(A[i]);
		A[i] = pq.top(); pq.pop();
	}
	while (q[a].size()) q[a].pop();
	for (int i = s; i <= e; ++i) {
		if (v < A[i]) swap(v, A[i]);
		q[a].push(A[i]);
	}
	return v;
}
int query(int s, int e, int v) {
	int a = (s - 1) / B + 1;
	int b = (e - 1) / B;
	if (b < a) return naive(s, e, v);
	v = naive(s, a * B, v);
	for (int i = a; i < b; ++i) {
		stk[i].push_back(v);
		q[i].push(v);
		v = q[i].top(); q[i].pop();
	}
	v = naive(b * B + 1, e, v);
	return v;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, Q; cin >> N >> Q;
	for (int i = 1; i <= N; ++i) {
		cin >> A[i];
		q[(i - 1) / B].push(A[i]);
	}
	while (Q--) {
		int s, t, p; cin >> s >> t >> p;
		int res;
		if (s <= t) res = query(s, t, p);
		else res = query(1, t, query(s, N, p));
		printf("%d\n", res);
	}
	return 0;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	128 ms	632 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	3181 ms	85996 KB	Output is correct
2	Correct	3156 ms	84580 KB	Output is correct
3	Correct	1757 ms	82424 KB	Output is correct
4	Correct	3104 ms	86000 KB	Output is correct
5	Correct	2266 ms	86128 KB	Output is correct
6	Correct	3027 ms	86132 KB	Output is correct
7	Correct	3019 ms	86052 KB	Output is correct
8	Correct	3001 ms	86076 KB	Output is correct
9	Correct	1549 ms	82552 KB	Output is correct
10	Correct	2381 ms	84792 KB	Output is correct
11	Correct	1504 ms	82552 KB	Output is correct
12	Correct	2407 ms	84664 KB	Output is correct
13	Correct	3115 ms	86136 KB	Output is correct
14	Correct	3118 ms	84660 KB	Output is correct
15	Correct	1761 ms	82500 KB	Output is correct
16	Correct	3121 ms	86064 KB	Output is correct
17	Correct	2372 ms	86008 KB	Output is correct
18	Correct	3155 ms	86264 KB	Output is correct
19	Correct	3184 ms	85880 KB	Output is correct
20	Correct	3199 ms	85896 KB	Output is correct

Subtask #3

0 / 80.0

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