답안 #55912 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55912	2018-07-09T07:21:54 Z	윤교준(#1564)	Sushi (JOI16_sushi)	C++11	100 / 100	5930 ms	122396 KB

sushi

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
const bool debug = 0;

const int MAXN = 400005;
const int MAXQ = 25005;
const int SQRN = 655;

struct BUK {
	priority_queue<int, vector<int>, greater<int>> QV;
	priority_queue<int> PQ;
	int A[SQRN];
	int S, E, N;

	int cal(int s, int e, int x) {
		for(int i = s; i <= e; i++)
			if(x < A[i]) swap(A[i], x);
		return x;
	}

	int f(int p, int q, int x) {
		p = max(S, p); q = min(E, q);
		if(p > q) return x;
		if(PQ.top() <= x) return x;
		if(p <= S && E <= q) {
			QV.push(x);
			int ret = PQ.top(); PQ.pop();
			PQ.push(x);
			return ret;
		}

		if(!QV.empty()) {
			for(int i = 0; i < N; i++) {
				if(A[i] <= QV.top()) continue;
				int t = QV.top(); QV.pop();
				QV.push(A[i]);
				A[i] = t;
			}
			for(; !QV.empty(); QV.pop());
		}

		int ret = cal(p-S, q-S, x);

		for(; !PQ.empty(); PQ.pop());
		for(int i = 0; i < N; i++)
			PQ.push(A[i]);

		return ret;
	}
} buk[SQRN]; int bukn;

int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];

int N, Q;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> Q;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= Q; i++) cin >> B[i] >> C[i] >> D[i];

	for(int i = 1, s, e;; i++) {
		s = (i-1)*SQRN + 1;
		e = min(N, i*SQRN);
		if(s > e) break;
		
		buk[i].S = s; buk[i].E = e;
		buk[i].N = e-s+1;
		for(int j = s; j <= e; j++) {
			buk[i].A[j-s] = A[j];
			buk[i].PQ.push(A[j]);
		}
		bukn = i;
	}

	if(debug) {
		printf("bukn=%d\n", bukn);
		for(int i = 1; i <= bukn; i++) {
			printf("%d buk : %d %d %d\n", i, buk[i].S, buk[i].E, buk[i].N);
			for(int j = 0; j < buk[i].N; j++) printf("%d ", buk[i].A[j]);
			puts("");
		}
	}

	for(int qi = 1, s, e, x; qi <= Q; qi++) {
		s = B[qi]; e = C[qi]; x = D[qi];

		if(s <= e) {
			for(int i = 1; i <= bukn; i++)
				x = buk[i].f(s, e, x);
		} else {
			for(int i = 1; i <= bukn; i++) {
				x = buk[i].f(s, N, x);
			}
			for(int i = 1; i <= bukn; i++)
				x = buk[i].f(1, e, x);
		}

		printf("%d\n", x);
	}
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	125 ms	2168 KB	Output is correct
2	Correct	122 ms	2348 KB	Output is correct
3	Correct	116 ms	2380 KB	Output is correct
4	Correct	133 ms	2380 KB	Output is correct
5	Correct	122 ms	2380 KB	Output is correct
6	Correct	131 ms	2380 KB	Output is correct
7	Correct	30 ms	2464 KB	Output is correct
8	Correct	29 ms	2464 KB	Output is correct
9	Correct	130 ms	2492 KB	Output is correct
10	Correct	119 ms	2512 KB	Output is correct
11	Correct	164 ms	2536 KB	Output is correct
12	Correct	162 ms	2536 KB	Output is correct
13	Correct	173 ms	2676 KB	Output is correct
14	Correct	102 ms	2676 KB	Output is correct
15	Correct	96 ms	2676 KB	Output is correct
16	Correct	131 ms	2676 KB	Output is correct
17	Correct	5 ms	2676 KB	Output is correct
18	Correct	3 ms	2676 KB	Output is correct
19	Correct	4 ms	2676 KB	Output is correct
20	Correct	3 ms	2676 KB	Output is correct
21	Correct	4 ms	2676 KB	Output is correct
22	Correct	4 ms	2676 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3162 ms	78064 KB	Output is correct
2	Correct	3024 ms	78064 KB	Output is correct
3	Correct	125 ms	78064 KB	Output is correct
4	Correct	3183 ms	78132 KB	Output is correct
5	Correct	2904 ms	78132 KB	Output is correct
6	Correct	3404 ms	78132 KB	Output is correct
7	Correct	3354 ms	78132 KB	Output is correct
8	Correct	3543 ms	78132 KB	Output is correct
9	Correct	120 ms	78132 KB	Output is correct
10	Correct	2871 ms	78132 KB	Output is correct
11	Correct	122 ms	78132 KB	Output is correct
12	Correct	2588 ms	78132 KB	Output is correct
13	Correct	2879 ms	78132 KB	Output is correct
14	Correct	3447 ms	78528 KB	Output is correct
15	Correct	124 ms	78528 KB	Output is correct
16	Correct	3020 ms	78584 KB	Output is correct
17	Correct	2824 ms	78584 KB	Output is correct
18	Correct	3608 ms	78584 KB	Output is correct
19	Correct	3408 ms	78584 KB	Output is correct
20	Correct	3385 ms	78584 KB	Output is correct

Subtask #3
80.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	125 ms	2168 KB	Output is correct
2	Correct	122 ms	2348 KB	Output is correct
3	Correct	116 ms	2380 KB	Output is correct
4	Correct	133 ms	2380 KB	Output is correct
5	Correct	122 ms	2380 KB	Output is correct
6	Correct	131 ms	2380 KB	Output is correct
7	Correct	30 ms	2464 KB	Output is correct
8	Correct	29 ms	2464 KB	Output is correct
9	Correct	130 ms	2492 KB	Output is correct
10	Correct	119 ms	2512 KB	Output is correct
11	Correct	164 ms	2536 KB	Output is correct
12	Correct	162 ms	2536 KB	Output is correct
13	Correct	173 ms	2676 KB	Output is correct
14	Correct	102 ms	2676 KB	Output is correct
15	Correct	96 ms	2676 KB	Output is correct
16	Correct	131 ms	2676 KB	Output is correct
17	Correct	5 ms	2676 KB	Output is correct
18	Correct	3 ms	2676 KB	Output is correct
19	Correct	4 ms	2676 KB	Output is correct
20	Correct	3 ms	2676 KB	Output is correct
21	Correct	4 ms	2676 KB	Output is correct
22	Correct	4 ms	2676 KB	Output is correct
23	Correct	3162 ms	78064 KB	Output is correct
24	Correct	3024 ms	78064 KB	Output is correct
25	Correct	125 ms	78064 KB	Output is correct
26	Correct	3183 ms	78132 KB	Output is correct
27	Correct	2904 ms	78132 KB	Output is correct
28	Correct	3404 ms	78132 KB	Output is correct
29	Correct	3354 ms	78132 KB	Output is correct
30	Correct	3543 ms	78132 KB	Output is correct
31	Correct	120 ms	78132 KB	Output is correct
32	Correct	2871 ms	78132 KB	Output is correct
33	Correct	122 ms	78132 KB	Output is correct
34	Correct	2588 ms	78132 KB	Output is correct
35	Correct	2879 ms	78132 KB	Output is correct
36	Correct	3447 ms	78528 KB	Output is correct
37	Correct	124 ms	78528 KB	Output is correct
38	Correct	3020 ms	78584 KB	Output is correct
39	Correct	2824 ms	78584 KB	Output is correct
40	Correct	3608 ms	78584 KB	Output is correct
41	Correct	3408 ms	78584 KB	Output is correct
42	Correct	3385 ms	78584 KB	Output is correct
43	Correct	1989 ms	78584 KB	Output is correct
44	Correct	1936 ms	78584 KB	Output is correct
45	Correct	527 ms	78584 KB	Output is correct
46	Correct	1941 ms	78584 KB	Output is correct
47	Correct	1937 ms	78584 KB	Output is correct
48	Correct	4755 ms	78584 KB	Output is correct
49	Correct	4546 ms	78584 KB	Output is correct
50	Correct	4925 ms	78584 KB	Output is correct
51	Correct	4934 ms	78584 KB	Output is correct
52	Correct	1972 ms	78584 KB	Output is correct
53	Correct	2041 ms	78584 KB	Output is correct
54	Correct	3985 ms	78584 KB	Output is correct
55	Correct	4430 ms	78584 KB	Output is correct
56	Correct	4066 ms	78584 KB	Output is correct
57	Correct	4206 ms	78584 KB	Output is correct
58	Correct	4304 ms	78584 KB	Output is correct
59	Correct	4142 ms	78584 KB	Output is correct
60	Correct	5531 ms	122396 KB	Output is correct
61	Correct	5784 ms	122396 KB	Output is correct
62	Correct	5917 ms	122396 KB	Output is correct
63	Correct	5930 ms	122396 KB	Output is correct
64	Correct	728 ms	122396 KB	Output is correct
65	Correct	1612 ms	122396 KB	Output is correct
66	Correct	1715 ms	122396 KB	Output is correct
67	Correct	3624 ms	122396 KB	Output is correct
68	Correct	3451 ms	122396 KB	Output is correct
69	Correct	3688 ms	122396 KB	Output is correct
70	Correct	3405 ms	122396 KB	Output is correct

답안 #55912

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 80.0 / 80.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
80.0 / 80.0