oj.uz

Submission #134845

# Submission time Handle Problem Language Result Execution time Memory
134845 2019-07-23T10:03:22 Z sebinkim Sushi (JOI16_sushi) C++14
100 / 100
 3072 ms 76340 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 504 KB Output is correct
2 Correct 22 ms 504 KB Output is correct
3 Correct 21 ms 504 KB Output is correct
4 Correct 22 ms 504 KB Output is correct
5 Correct 21 ms 376 KB Output is correct
6 Correct 22 ms 376 KB Output is correct
7 Correct 17 ms 376 KB Output is correct
8 Correct 17 ms 376 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 23 ms 504 KB Output is correct
11 Correct 25 ms 632 KB Output is correct
12 Correct 25 ms 504 KB Output is correct
13 Correct 26 ms 508 KB Output is correct
14 Correct 17 ms 504 KB Output is correct
15 Correct 17 ms 504 KB Output is correct
16 Correct 13 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2779 ms 76060 KB Output is correct
2 Correct 2758 ms 74528 KB Output is correct
3 Correct 253 ms 6460 KB Output is correct
4 Correct 2809 ms 75964 KB Output is correct
5 Correct 2400 ms 75624 KB Output is correct
6 Correct 2938 ms 75536 KB Output is correct
7 Correct 3021 ms 75580 KB Output is correct
8 Correct 3020 ms 75612 KB Output is correct
9 Correct 254 ms 6268 KB Output is correct
10 Correct 2295 ms 70332 KB Output is correct
11 Correct 252 ms 6136 KB Output is correct
12 Correct 2277 ms 71388 KB Output is correct
13 Correct 2806 ms 76340 KB Output is correct
14 Correct 2775 ms 75096 KB Output is correct
15 Correct 256 ms 6392 KB Output is correct
16 Correct 2785 ms 76220 KB Output is correct
17 Correct 2408 ms 75676 KB Output is correct
18 Correct 2979 ms 75620 KB Output is correct
19 Correct 2952 ms 75664 KB Output is correct
20 Correct 2895 ms 75672 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 504 KB Output is correct
2 Correct 22 ms 504 KB Output is correct
3 Correct 21 ms 504 KB Output is correct
4 Correct 22 ms 504 KB Output is correct
5 Correct 21 ms 376 KB Output is correct
6 Correct 22 ms 376 KB Output is correct
7 Correct 17 ms 376 KB Output is correct
8 Correct 17 ms 376 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 23 ms 504 KB Output is correct
11 Correct 25 ms 632 KB Output is correct
12 Correct 25 ms 504 KB Output is correct
13 Correct 26 ms 508 KB Output is correct
14 Correct 17 ms 504 KB Output is correct
15 Correct 17 ms 504 KB Output is correct
16 Correct 13 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2779 ms 76060 KB Output is correct
24 Correct 2758 ms 74528 KB Output is correct
25 Correct 253 ms 6460 KB Output is correct
26 Correct 2809 ms 75964 KB Output is correct
27 Correct 2400 ms 75624 KB Output is correct
28 Correct 2938 ms 75536 KB Output is correct
29 Correct 3021 ms 75580 KB Output is correct
30 Correct 3020 ms 75612 KB Output is correct
31 Correct 254 ms 6268 KB Output is correct
32 Correct 2295 ms 70332 KB Output is correct
33 Correct 252 ms 6136 KB Output is correct
34 Correct 2277 ms 71388 KB Output is correct
35 Correct 2806 ms 76340 KB Output is correct
36 Correct 2775 ms 75096 KB Output is correct
37 Correct 256 ms 6392 KB Output is correct
38 Correct 2785 ms 76220 KB Output is correct
39 Correct 2408 ms 75676 KB Output is correct
40 Correct 2979 ms 75620 KB Output is correct
41 Correct 2952 ms 75664 KB Output is correct
42 Correct 2895 ms 75672 KB Output is correct
43 Correct 861 ms 10336 KB Output is correct
44 Correct 886 ms 10376 KB Output is correct
45 Correct 515 ms 6388 KB Output is correct
46 Correct 861 ms 10288 KB Output is correct
47 Correct 852 ms 10380 KB Output is correct
48 Correct 2812 ms 11764 KB Output is correct
49 Correct 2902 ms 11860 KB Output is correct
50 Correct 2849 ms 11808 KB Output is correct
51 Correct 2880 ms 11640 KB Output is correct
52 Correct 752 ms 11184 KB Output is correct
53 Correct 754 ms 10900 KB Output is correct
54 Correct 2618 ms 14076 KB Output is correct
55 Correct 2752 ms 13816 KB Output is correct
56 Correct 2759 ms 13952 KB Output is correct
57 Correct 2721 ms 13908 KB Output is correct
58 Correct 2567 ms 14096 KB Output is correct
59 Correct 2611 ms 14236 KB Output is correct
60 Correct 2522 ms 75668 KB Output is correct
61 Correct 3072 ms 75636 KB Output is correct
62 Correct 3030 ms 75560 KB Output is correct
63 Correct 2989 ms 75840 KB Output is correct
64 Correct 372 ms 6528 KB Output is correct
65 Correct 1240 ms 40372 KB Output is correct
66 Correct 1222 ms 40656 KB Output is correct
67 Correct 1694 ms 45816 KB Output is correct
68 Correct 1999 ms 45944 KB Output is correct
69 Correct 1987 ms 45780 KB Output is correct
70 Correct 1959 ms 45872 KB Output is correct