답안 #55129 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55129	2018-07-06T05:48:51 Z	ainta(#1558)	Sushi (JOI16_sushi)	C++11	100 / 100	6783 ms	95636 KB

sushi

#include<cstdio>
#include<algorithm>
#include<queue>
#define BB 9
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	221 ms	1876 KB	Output is correct
2	Correct	180 ms	2164 KB	Output is correct
3	Correct	171 ms	2164 KB	Output is correct
4	Correct	173 ms	2164 KB	Output is correct
5	Correct	184 ms	2252 KB	Output is correct
6	Correct	181 ms	2312 KB	Output is correct
7	Correct	121 ms	2312 KB	Output is correct
8	Correct	125 ms	2312 KB	Output is correct
9	Correct	174 ms	2312 KB	Output is correct
10	Correct	186 ms	2312 KB	Output is correct
11	Correct	204 ms	2312 KB	Output is correct
12	Correct	195 ms	2312 KB	Output is correct
13	Correct	210 ms	2312 KB	Output is correct
14	Correct	239 ms	2312 KB	Output is correct
15	Correct	208 ms	2312 KB	Output is correct
16	Correct	117 ms	2312 KB	Output is correct
17	Correct	3 ms	2312 KB	Output is correct
18	Correct	3 ms	2312 KB	Output is correct
19	Correct	4 ms	2312 KB	Output is correct
20	Correct	4 ms	2312 KB	Output is correct
21	Correct	5 ms	2312 KB	Output is correct
22	Correct	3 ms	2312 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2956 ms	95528 KB	Output is correct
2	Correct	3109 ms	95528 KB	Output is correct
3	Correct	2020 ms	95528 KB	Output is correct
4	Correct	2951 ms	95588 KB	Output is correct
5	Correct	2161 ms	95588 KB	Output is correct
6	Correct	2790 ms	95636 KB	Output is correct
7	Correct	3045 ms	95636 KB	Output is correct
8	Correct	2620 ms	95636 KB	Output is correct
9	Correct	2246 ms	95636 KB	Output is correct
10	Correct	2584 ms	95636 KB	Output is correct
11	Correct	2029 ms	95636 KB	Output is correct
12	Correct	2223 ms	95636 KB	Output is correct
13	Correct	2940 ms	95636 KB	Output is correct
14	Correct	3106 ms	95636 KB	Output is correct
15	Correct	2272 ms	95636 KB	Output is correct
16	Correct	2823 ms	95636 KB	Output is correct
17	Correct	2013 ms	95636 KB	Output is correct
18	Correct	2656 ms	95636 KB	Output is correct
19	Correct	2553 ms	95636 KB	Output is correct
20	Correct	2479 ms	95636 KB	Output is correct

Subtask #3
80.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	1876 KB	Output is correct
2	Correct	180 ms	2164 KB	Output is correct
3	Correct	171 ms	2164 KB	Output is correct
4	Correct	173 ms	2164 KB	Output is correct
5	Correct	184 ms	2252 KB	Output is correct
6	Correct	181 ms	2312 KB	Output is correct
7	Correct	121 ms	2312 KB	Output is correct
8	Correct	125 ms	2312 KB	Output is correct
9	Correct	174 ms	2312 KB	Output is correct
10	Correct	186 ms	2312 KB	Output is correct
11	Correct	204 ms	2312 KB	Output is correct
12	Correct	195 ms	2312 KB	Output is correct
13	Correct	210 ms	2312 KB	Output is correct
14	Correct	239 ms	2312 KB	Output is correct
15	Correct	208 ms	2312 KB	Output is correct
16	Correct	117 ms	2312 KB	Output is correct
17	Correct	3 ms	2312 KB	Output is correct
18	Correct	3 ms	2312 KB	Output is correct
19	Correct	4 ms	2312 KB	Output is correct
20	Correct	4 ms	2312 KB	Output is correct
21	Correct	5 ms	2312 KB	Output is correct
22	Correct	3 ms	2312 KB	Output is correct
23	Correct	2956 ms	95528 KB	Output is correct
24	Correct	3109 ms	95528 KB	Output is correct
25	Correct	2020 ms	95528 KB	Output is correct
26	Correct	2951 ms	95588 KB	Output is correct
27	Correct	2161 ms	95588 KB	Output is correct
28	Correct	2790 ms	95636 KB	Output is correct
29	Correct	3045 ms	95636 KB	Output is correct
30	Correct	2620 ms	95636 KB	Output is correct
31	Correct	2246 ms	95636 KB	Output is correct
32	Correct	2584 ms	95636 KB	Output is correct
33	Correct	2029 ms	95636 KB	Output is correct
34	Correct	2223 ms	95636 KB	Output is correct
35	Correct	2940 ms	95636 KB	Output is correct
36	Correct	3106 ms	95636 KB	Output is correct
37	Correct	2272 ms	95636 KB	Output is correct
38	Correct	2823 ms	95636 KB	Output is correct
39	Correct	2013 ms	95636 KB	Output is correct
40	Correct	2656 ms	95636 KB	Output is correct
41	Correct	2553 ms	95636 KB	Output is correct
42	Correct	2479 ms	95636 KB	Output is correct
43	Correct	4657 ms	95636 KB	Output is correct
44	Correct	4534 ms	95636 KB	Output is correct
45	Correct	3708 ms	95636 KB	Output is correct
46	Correct	4779 ms	95636 KB	Output is correct
47	Correct	5239 ms	95636 KB	Output is correct
48	Correct	5352 ms	95636 KB	Output is correct
49	Correct	5856 ms	95636 KB	Output is correct
50	Correct	5442 ms	95636 KB	Output is correct
51	Correct	5895 ms	95636 KB	Output is correct
52	Correct	6121 ms	95636 KB	Output is correct
53	Correct	5730 ms	95636 KB	Output is correct
54	Correct	6094 ms	95636 KB	Output is correct
55	Correct	6717 ms	95636 KB	Output is correct
56	Correct	6614 ms	95636 KB	Output is correct
57	Correct	6783 ms	95636 KB	Output is correct
58	Correct	3405 ms	95636 KB	Output is correct
59	Correct	4252 ms	95636 KB	Output is correct
60	Correct	4488 ms	95636 KB	Output is correct
61	Correct	4852 ms	95636 KB	Output is correct
62	Correct	4638 ms	95636 KB	Output is correct
63	Correct	5140 ms	95636 KB	Output is correct
64	Correct	2519 ms	95636 KB	Output is correct
65	Correct	2850 ms	95636 KB	Output is correct
66	Correct	3014 ms	95636 KB	Output is correct
67	Correct	5128 ms	95636 KB	Output is correct
68	Correct	5716 ms	95636 KB	Output is correct
69	Correct	5368 ms	95636 KB	Output is correct
70	Correct	5147 ms	95636 KB	Output is correct

답안 #55129

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