답안 #55121 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55121	2018-07-06T05:27:26 Z	ainta	Sushi (JOI16_sushi)	C++17	100 / 100	8726 ms	50940 KB

sushi

#include<cstdio>
#include<algorithm>
#include<queue>
#define BB 10
using namespace std;
int n, Q;
struct point {
	int P[1 << BB], SZ;
	vector<int>U;
	priority_queue<int>PQ;
	void Make() {
		int i;
		while (!PQ.empty())PQ.pop();
		for (i = 0; i < SZ; i++) {
			PQ.push(P[i]);
		}
	}
	void init() {
		priority_queue<int>PP;
		for (auto &t : U) {
			PP.push(-t);
		}
		int i;
		for (i = 0; i < SZ; i++) {
			PP.push(-P[i]);
			P[i] = -PP.top();
			PP.pop();
		}
		U.clear();
	}
	int Go(int x) {
		U.push_back(x);
		PQ.push(x);
		int ret = PQ.top();
		PQ.pop();
		return ret;
	}
}w[(400000 >> BB) + 2];
int Do(int b, int e, int x) {
	for (int i = (b >> BB); i <= (e >> BB); i++) {
		int bb = (i << BB), ee = min(((i + 1) << BB) - 1, n - 1);
		if (b <= bb && ee <= e) {
			x = w[i].Go(x);
		}
		else {
			w[i].init();
			bb = max(b, bb)&((1 << BB) - 1);
			ee = min(e, ee)&((1 << BB) - 1);
			for (int j = bb; j <= ee; j++) {
				if (w[i].P[j] > x) {
					swap(w[i].P[j], x);
				}
			}
			w[i].Make();
		}
	}
	return x;
}
int main() {
	int i, b, e, c;
	scanf("%d%d", &n, &Q);
	for (i = 0; i < n; i++) {
		scanf("%d", &w[i >> BB].P[i&((1 << BB) - 1)]);
		w[i >> BB].SZ++;
	}
	for (i = 0; i <= ((n - 1) >> BB); i++)w[i].Make();
	while (Q--) {
		scanf("%d%d%d", &b, &e, &c);
		b--, e--;
		if (b > e) {
			printf("%d\n", Do(0, e, Do(b, n - 1, c)));
		}
		else {
			printf("%d\n", Do(b, e, c));
		}
	}
	return 0;
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
telegraph.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i >> BB].P[i&((1 << BB) - 1)]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &b, &e, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	347 ms	2040 KB	Output is correct
2	Correct	374 ms	2040 KB	Output is correct
3	Correct	352 ms	2092 KB	Output is correct
4	Correct	387 ms	2128 KB	Output is correct
5	Correct	363 ms	2248 KB	Output is correct
6	Correct	405 ms	2248 KB	Output is correct
7	Correct	168 ms	2248 KB	Output is correct
8	Correct	191 ms	2248 KB	Output is correct
9	Correct	403 ms	2264 KB	Output is correct
10	Correct	371 ms	2264 KB	Output is correct
11	Correct	382 ms	2320 KB	Output is correct
12	Correct	385 ms	2320 KB	Output is correct
13	Correct	400 ms	2320 KB	Output is correct
14	Correct	466 ms	2320 KB	Output is correct
15	Correct	440 ms	2368 KB	Output is correct
16	Correct	225 ms	2368 KB	Output is correct
17	Correct	3 ms	2368 KB	Output is correct
18	Correct	3 ms	2368 KB	Output is correct
19	Correct	4 ms	2368 KB	Output is correct
20	Correct	3 ms	2368 KB	Output is correct
21	Correct	4 ms	2368 KB	Output is correct
22	Correct	3 ms	2368 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1795 ms	50792 KB	Output is correct
2	Correct	1854 ms	50940 KB	Output is correct
3	Correct	1283 ms	50940 KB	Output is correct
4	Correct	1646 ms	50940 KB	Output is correct
5	Correct	1294 ms	50940 KB	Output is correct
6	Correct	1378 ms	50940 KB	Output is correct
7	Correct	1400 ms	50940 KB	Output is correct
8	Correct	1582 ms	50940 KB	Output is correct
9	Correct	1314 ms	50940 KB	Output is correct
10	Correct	1459 ms	50940 KB	Output is correct
11	Correct	1385 ms	50940 KB	Output is correct
12	Correct	1249 ms	50940 KB	Output is correct
13	Correct	1861 ms	50940 KB	Output is correct
14	Correct	1745 ms	50940 KB	Output is correct
15	Correct	1526 ms	50940 KB	Output is correct
16	Correct	1947 ms	50940 KB	Output is correct
17	Correct	1333 ms	50940 KB	Output is correct
18	Correct	1518 ms	50940 KB	Output is correct
19	Correct	1556 ms	50940 KB	Output is correct
20	Correct	1778 ms	50940 KB	Output is correct

Subtask #3
80.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	347 ms	2040 KB	Output is correct
2	Correct	374 ms	2040 KB	Output is correct
3	Correct	352 ms	2092 KB	Output is correct
4	Correct	387 ms	2128 KB	Output is correct
5	Correct	363 ms	2248 KB	Output is correct
6	Correct	405 ms	2248 KB	Output is correct
7	Correct	168 ms	2248 KB	Output is correct
8	Correct	191 ms	2248 KB	Output is correct
9	Correct	403 ms	2264 KB	Output is correct
10	Correct	371 ms	2264 KB	Output is correct
11	Correct	382 ms	2320 KB	Output is correct
12	Correct	385 ms	2320 KB	Output is correct
13	Correct	400 ms	2320 KB	Output is correct
14	Correct	466 ms	2320 KB	Output is correct
15	Correct	440 ms	2368 KB	Output is correct
16	Correct	225 ms	2368 KB	Output is correct
17	Correct	3 ms	2368 KB	Output is correct
18	Correct	3 ms	2368 KB	Output is correct
19	Correct	4 ms	2368 KB	Output is correct
20	Correct	3 ms	2368 KB	Output is correct
21	Correct	4 ms	2368 KB	Output is correct
22	Correct	3 ms	2368 KB	Output is correct
23	Correct	1795 ms	50792 KB	Output is correct
24	Correct	1854 ms	50940 KB	Output is correct
25	Correct	1283 ms	50940 KB	Output is correct
26	Correct	1646 ms	50940 KB	Output is correct
27	Correct	1294 ms	50940 KB	Output is correct
28	Correct	1378 ms	50940 KB	Output is correct
29	Correct	1400 ms	50940 KB	Output is correct
30	Correct	1582 ms	50940 KB	Output is correct
31	Correct	1314 ms	50940 KB	Output is correct
32	Correct	1459 ms	50940 KB	Output is correct
33	Correct	1385 ms	50940 KB	Output is correct
34	Correct	1249 ms	50940 KB	Output is correct
35	Correct	1861 ms	50940 KB	Output is correct
36	Correct	1745 ms	50940 KB	Output is correct
37	Correct	1526 ms	50940 KB	Output is correct
38	Correct	1947 ms	50940 KB	Output is correct
39	Correct	1333 ms	50940 KB	Output is correct
40	Correct	1518 ms	50940 KB	Output is correct
41	Correct	1556 ms	50940 KB	Output is correct
42	Correct	1778 ms	50940 KB	Output is correct
43	Correct	8115 ms	50940 KB	Output is correct
44	Correct	7906 ms	50940 KB	Output is correct
45	Correct	5092 ms	50940 KB	Output is correct
46	Correct	7693 ms	50940 KB	Output is correct
47	Correct	8273 ms	50940 KB	Output is correct
48	Correct	7618 ms	50940 KB	Output is correct
49	Correct	8455 ms	50940 KB	Output is correct
50	Correct	8726 ms	50940 KB	Output is correct
51	Correct	8598 ms	50940 KB	Output is correct
52	Correct	8086 ms	50940 KB	Output is correct
53	Correct	7556 ms	50940 KB	Output is correct
54	Correct	7715 ms	50940 KB	Output is correct
55	Correct	8200 ms	50940 KB	Output is correct
56	Correct	7956 ms	50940 KB	Output is correct
57	Correct	8060 ms	50940 KB	Output is correct
58	Correct	4734 ms	50940 KB	Output is correct
59	Correct	4743 ms	50940 KB	Output is correct
60	Correct	5466 ms	50940 KB	Output is correct
61	Correct	5460 ms	50940 KB	Output is correct
62	Correct	5801 ms	50940 KB	Output is correct
63	Correct	5218 ms	50940 KB	Output is correct
64	Correct	4157 ms	50940 KB	Output is correct
65	Correct	4529 ms	50940 KB	Output is correct
66	Correct	4321 ms	50940 KB	Output is correct
67	Correct	6140 ms	50940 KB	Output is correct
68	Correct	6753 ms	50940 KB	Output is correct
69	Correct	6704 ms	50940 KB	Output is correct
70	Correct	6631 ms	50940 KB	Output is correct

답안 #55121

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