oj.uz

답안 #202638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202638 2020-02-17T12:05:06 Z maruii Sushi (JOI16_sushi) C++14
100 / 100
 7194 ms 85948 KB 
#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]);
	for (int i = a * B + 1; i <= a * B + B; ++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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 504 KB Output is correct
2 Correct 213 ms 536 KB Output is correct
3 Correct 218 ms 632 KB Output is correct
4 Correct 215 ms 504 KB Output is correct
5 Correct 214 ms 376 KB Output is correct
6 Correct 219 ms 504 KB Output is correct
7 Correct 101 ms 376 KB Output is correct
8 Correct 102 ms 376 KB Output is correct
9 Correct 217 ms 504 KB Output is correct
10 Correct 209 ms 504 KB Output is correct
11 Correct 210 ms 504 KB Output is correct
12 Correct 212 ms 504 KB Output is correct
13 Correct 224 ms 760 KB Output is correct
14 Correct 290 ms 644 KB Output is correct
15 Correct 284 ms 632 KB Output is correct
16 Correct 94 ms 632 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3348 ms 81528 KB Output is correct
2 Correct 3316 ms 81656 KB Output is correct
3 Correct 1974 ms 81784 KB Output is correct
4 Correct 3338 ms 81760 KB Output is correct
5 Correct 2643 ms 81912 KB Output is correct
6 Correct 3386 ms 81900 KB Output is correct
7 Correct 3364 ms 82048 KB Output is correct
8 Correct 3323 ms 82080 KB Output is correct
9 Correct 1802 ms 81428 KB Output is correct
10 Correct 2646 ms 81760 KB Output is correct
11 Correct 1763 ms 81656 KB Output is correct
12 Correct 2697 ms 81804 KB Output is correct
13 Correct 3354 ms 81912 KB Output is correct
14 Correct 3319 ms 81656 KB Output is correct
15 Correct 2017 ms 81400 KB Output is correct
16 Correct 3344 ms 81948 KB Output is correct
17 Correct 2607 ms 81784 KB Output is correct
18 Correct 3413 ms 82080 KB Output is correct
19 Correct 3335 ms 81664 KB Output is correct
20 Correct 3337 ms 81832 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 504 KB Output is correct
2 Correct 213 ms 536 KB Output is correct
3 Correct 218 ms 632 KB Output is correct
4 Correct 215 ms 504 KB Output is correct
5 Correct 214 ms 376 KB Output is correct
6 Correct 219 ms 504 KB Output is correct
7 Correct 101 ms 376 KB Output is correct
8 Correct 102 ms 376 KB Output is correct
9 Correct 217 ms 504 KB Output is correct
10 Correct 209 ms 504 KB Output is correct
11 Correct 210 ms 504 KB Output is correct
12 Correct 212 ms 504 KB Output is correct
13 Correct 224 ms 760 KB Output is correct
14 Correct 290 ms 644 KB Output is correct
15 Correct 284 ms 632 KB Output is correct
16 Correct 94 ms 632 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 3348 ms 81528 KB Output is correct
24 Correct 3316 ms 81656 KB Output is correct
25 Correct 1974 ms 81784 KB Output is correct
26 Correct 3338 ms 81760 KB Output is correct
27 Correct 2643 ms 81912 KB Output is correct
28 Correct 3386 ms 81900 KB Output is correct
29 Correct 3364 ms 82048 KB Output is correct
30 Correct 3323 ms 82080 KB Output is correct
31 Correct 1802 ms 81428 KB Output is correct
32 Correct 2646 ms 81760 KB Output is correct
33 Correct 1763 ms 81656 KB Output is correct
34 Correct 2697 ms 81804 KB Output is correct
35 Correct 3354 ms 81912 KB Output is correct
36 Correct 3319 ms 81656 KB Output is correct
37 Correct 2017 ms 81400 KB Output is correct
38 Correct 3344 ms 81948 KB Output is correct
39 Correct 2607 ms 81784 KB Output is correct
40 Correct 3413 ms 82080 KB Output is correct
41 Correct 3335 ms 81664 KB Output is correct
42 Correct 3337 ms 81832 KB Output is correct
43 Correct 5155 ms 12972 KB Output is correct
44 Correct 5178 ms 12800 KB Output is correct
45 Correct 3042 ms 9080 KB Output is correct
46 Correct 5130 ms 12804 KB Output is correct
47 Correct 5158 ms 12928 KB Output is correct
48 Correct 5265 ms 13000 KB Output is correct
49 Correct 5789 ms 12960 KB Output is correct
50 Correct 5749 ms 12752 KB Output is correct
51 Correct 5749 ms 12920 KB Output is correct
52 Correct 6432 ms 20640 KB Output is correct
53 Correct 6303 ms 19836 KB Output is correct
54 Correct 6340 ms 20092 KB Output is correct
55 Correct 6983 ms 19880 KB Output is correct
56 Correct 7194 ms 19836 KB Output is correct
57 Correct 6952 ms 20028 KB Output is correct
58 Correct 3768 ms 15172 KB Output is correct
59 Correct 3666 ms 15512 KB Output is correct
60 Correct 2854 ms 85900 KB Output is correct
61 Correct 3460 ms 85948 KB Output is correct
62 Correct 3416 ms 85880 KB Output is correct
63 Correct 3373 ms 85944 KB Output is correct
64 Correct 2178 ms 9336 KB Output is correct
65 Correct 2404 ms 47224 KB Output is correct
66 Correct 2423 ms 46968 KB Output is correct
67 Correct 4939 ms 72508 KB Output is correct
68 Correct 5659 ms 72116 KB Output is correct
69 Correct 5708 ms 72116 KB Output is correct
70 Correct 5599 ms 72536 KB Output is correct