답안 #55945 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55945	2018-07-09T08:00:02 Z	김세빈(#1563)	Sushi (JOI16_sushi)	C++11	100 / 100	3806 ms	72480 KB

sushi

#include <bits/stdc++.h>

using namespace std;

int sz = 700;

int A[404040], H[404040];
int B[404040], L[1010], R[1010];
priority_queue <int, vector<int>, greater<int>> Q[1010];
int n, k;

void spread(int x)
{
	if(Q[x].empty()) return;
	
	int i;
	
	for(i=L[x];i<=R[x];i++){
		if(A[i] > Q[x].top()){
			Q[x].push(A[i]);
			A[i] = Q[x].top(); Q[x].pop();
		}
	}
	
	for(;!Q[x].empty();) Q[x].pop();
}

int main()
{
	int q, i, a, b, c, x, y;
	
	scanf("%d%d", &n, &q);
	
	for(i=0;i<n;i++){
		scanf("%d", A+i);
		H[i] = A[i]; B[i] = i/sz;
		if(i % sz == 0) L[i/sz] = i;
		R[i/sz] = i;
	}
	
	k = (n - 1) / sz + 1;
	
	for(i=0;i<k;i++){
		make_heap(H + L[i], H + R[i] + 1);
	}
	
	for(;q--;){
		scanf("%d%d%d", &a, &b, &c);
		a --, b --;
		x = B[a], y = B[b];
		
		if(x == y){
			if(a <= b){
				spread(x);
				for(i=a;i<=b;i++){
					if(A[i] > c) swap(A[i], c);
				}
				
				for(i=L[x];i<=R[x];i++) H[i] = A[i];
				make_heap(H + L[x], H + R[x] + 1);
				
				printf("%d\n", c);
			}
			else{
				spread(x);
				for(i=a;i<=R[x];i++){
					if(A[i] > c) swap(A[i], c);
				}
				x = (x + 1) % k;
				
				for(;x!=y;x=(x+1)%k){
					if(H[L[x]] > c){
						Q[x].push(c);
						pop_heap(H + L[x], H + R[x] + 1);
						swap(c, H[R[x]]);
						push_heap(H + L[x], H + R[x] + 1);
					}
				}
				
				for(i=L[x];i<=b;i++){
					if(A[i] > c) swap(A[i], c);
				}
				
				for(i=L[x];i<=R[x];i++) H[i] = A[i];
				make_heap(H + L[x], H + R[x] + 1);
				
				printf("%d\n", c);
			}
		}
		else{
			if(L[x] != a){
				spread(x);
				
				for(i=a;i<=R[x];i++){
					if(A[i] > c) swap(A[i], c);
				}
				
				for(i=L[x];i<=R[x];i++) H[i] = A[i];
				make_heap(H + L[x], H + R[x] + 1);
				
				x = (x + 1) % k;
			}
			
			
			for(;x!=y;x=(x+1)%k){
				if(H[L[x]] > c){
					Q[x].push(c);
					pop_heap(H + L[x], H + R[x] + 1);
					swap(c, H[R[x]]);
					push_heap(H + L[x], H + R[x] + 1);
				}
			}
					
			spread(y);
			for(i=L[y];i<=b;i++){
				if(A[i] > c) swap(A[i], c);
			}
			
			for(i=L[y];i<=R[y];i++) H[i] = A[i];
			make_heap(H + L[y], H + R[y] + 1);

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

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:32: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:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~
telegraph.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	380 KB	Output is correct
2	Correct	29 ms	508 KB	Output is correct
3	Correct	24 ms	508 KB	Output is correct
4	Correct	25 ms	540 KB	Output is correct
5	Correct	25 ms	604 KB	Output is correct
6	Correct	27 ms	604 KB	Output is correct
7	Correct	22 ms	604 KB	Output is correct
8	Correct	21 ms	616 KB	Output is correct
9	Correct	24 ms	664 KB	Output is correct
10	Correct	31 ms	824 KB	Output is correct
11	Correct	36 ms	824 KB	Output is correct
12	Correct	32 ms	824 KB	Output is correct
13	Correct	40 ms	824 KB	Output is correct
14	Correct	21 ms	824 KB	Output is correct
15	Correct	25 ms	824 KB	Output is correct
16	Correct	15 ms	824 KB	Output is correct
17	Correct	2 ms	824 KB	Output is correct
18	Correct	2 ms	824 KB	Output is correct
19	Correct	3 ms	824 KB	Output is correct
20	Correct	3 ms	824 KB	Output is correct
21	Correct	3 ms	824 KB	Output is correct
22	Correct	2 ms	824 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3438 ms	72148 KB	Output is correct
2	Correct	3585 ms	72148 KB	Output is correct
3	Correct	320 ms	72148 KB	Output is correct
4	Correct	3692 ms	72148 KB	Output is correct
5	Correct	3327 ms	72148 KB	Output is correct
6	Correct	3532 ms	72148 KB	Output is correct
7	Correct	3806 ms	72148 KB	Output is correct
8	Correct	3646 ms	72148 KB	Output is correct
9	Correct	330 ms	72148 KB	Output is correct
10	Correct	2829 ms	72148 KB	Output is correct
11	Correct	254 ms	72148 KB	Output is correct
12	Correct	2758 ms	72148 KB	Output is correct
13	Correct	3370 ms	72480 KB	Output is correct
14	Correct	3053 ms	72480 KB	Output is correct
15	Correct	284 ms	72480 KB	Output is correct
16	Correct	3209 ms	72480 KB	Output is correct
17	Correct	2451 ms	72480 KB	Output is correct
18	Correct	3138 ms	72480 KB	Output is correct
19	Correct	3348 ms	72480 KB	Output is correct
20	Correct	3041 ms	72480 KB	Output is correct

Subtask #3
80.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	380 KB	Output is correct
2	Correct	29 ms	508 KB	Output is correct
3	Correct	24 ms	508 KB	Output is correct
4	Correct	25 ms	540 KB	Output is correct
5	Correct	25 ms	604 KB	Output is correct
6	Correct	27 ms	604 KB	Output is correct
7	Correct	22 ms	604 KB	Output is correct
8	Correct	21 ms	616 KB	Output is correct
9	Correct	24 ms	664 KB	Output is correct
10	Correct	31 ms	824 KB	Output is correct
11	Correct	36 ms	824 KB	Output is correct
12	Correct	32 ms	824 KB	Output is correct
13	Correct	40 ms	824 KB	Output is correct
14	Correct	21 ms	824 KB	Output is correct
15	Correct	25 ms	824 KB	Output is correct
16	Correct	15 ms	824 KB	Output is correct
17	Correct	2 ms	824 KB	Output is correct
18	Correct	2 ms	824 KB	Output is correct
19	Correct	3 ms	824 KB	Output is correct
20	Correct	3 ms	824 KB	Output is correct
21	Correct	3 ms	824 KB	Output is correct
22	Correct	2 ms	824 KB	Output is correct
23	Correct	3438 ms	72148 KB	Output is correct
24	Correct	3585 ms	72148 KB	Output is correct
25	Correct	320 ms	72148 KB	Output is correct
26	Correct	3692 ms	72148 KB	Output is correct
27	Correct	3327 ms	72148 KB	Output is correct
28	Correct	3532 ms	72148 KB	Output is correct
29	Correct	3806 ms	72148 KB	Output is correct
30	Correct	3646 ms	72148 KB	Output is correct
31	Correct	330 ms	72148 KB	Output is correct
32	Correct	2829 ms	72148 KB	Output is correct
33	Correct	254 ms	72148 KB	Output is correct
34	Correct	2758 ms	72148 KB	Output is correct
35	Correct	3370 ms	72480 KB	Output is correct
36	Correct	3053 ms	72480 KB	Output is correct
37	Correct	284 ms	72480 KB	Output is correct
38	Correct	3209 ms	72480 KB	Output is correct
39	Correct	2451 ms	72480 KB	Output is correct
40	Correct	3138 ms	72480 KB	Output is correct
41	Correct	3348 ms	72480 KB	Output is correct
42	Correct	3041 ms	72480 KB	Output is correct
43	Correct	905 ms	72480 KB	Output is correct
44	Correct	928 ms	72480 KB	Output is correct
45	Correct	491 ms	72480 KB	Output is correct
46	Correct	858 ms	72480 KB	Output is correct
47	Correct	966 ms	72480 KB	Output is correct
48	Correct	2940 ms	72480 KB	Output is correct
49	Correct	3246 ms	72480 KB	Output is correct
50	Correct	3277 ms	72480 KB	Output is correct
51	Correct	3143 ms	72480 KB	Output is correct
52	Correct	824 ms	72480 KB	Output is correct
53	Correct	755 ms	72480 KB	Output is correct
54	Correct	2803 ms	72480 KB	Output is correct
55	Correct	2977 ms	72480 KB	Output is correct
56	Correct	2824 ms	72480 KB	Output is correct
57	Correct	3101 ms	72480 KB	Output is correct
58	Correct	2954 ms	72480 KB	Output is correct
59	Correct	2941 ms	72480 KB	Output is correct
60	Correct	2865 ms	72480 KB	Output is correct
61	Correct	3334 ms	72480 KB	Output is correct
62	Correct	3317 ms	72480 KB	Output is correct
63	Correct	3497 ms	72480 KB	Output is correct
64	Correct	416 ms	72480 KB	Output is correct
65	Correct	1437 ms	72480 KB	Output is correct
66	Correct	1432 ms	72480 KB	Output is correct
67	Correct	1924 ms	72480 KB	Output is correct
68	Correct	2219 ms	72480 KB	Output is correct
69	Correct	2087 ms	72480 KB	Output is correct
70	Correct	2023 ms	72480 KB	Output is correct

답안 #55945

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