oj.uz

Submission #134632

# Submission time Handle Problem Language Result Execution time Memory
134632 2019-07-23T06:00:27 Z 이온조(#3239) Sushi (JOI16_sushi) C++14
100 / 100
 4570 ms 82316 KB 
#include <bits/stdc++.h>
using namespace std;

const int sn = 632;
int N, X[400009];
priority_queue<int> pq[700], L[700];

inline int geti(int i) { return (i-1) / sn; }

void go(int s, int e, int &x) {
	if(s > e) return;
	int id = geti(s), bs = id*sn+1, be = min(bs + sn - 1, N);
	if(s != bs || e < be) {
		for(int i=bs; i<=be; i++) {
			L[id].push(-X[i]);
			X[i] = -L[id].top();
			L[id].pop();
		}
		L[id] = pq[id] = priority_queue<int>();
		for(int i=s; i<=min(be, e); i++) if(X[i] > x) swap(x, X[i]);
		for(int i=bs; i<=be; i++) pq[id].push(X[i]);
		go(be + 1, e, x);
	}
	else {
		L[id].push(-x);
		pq[id].push(x);
		x = pq[id].top(); pq[id].pop();
		go(be + 1, e, x);
	}
}

int main() {
	int Q; scanf("%d%d",&N,&Q);
	for(int i=1; i<=N; i++) {
		scanf("%d",&X[i]);
		pq[geti(i)].push(X[i]);
	}
	while(Q--) {
		int S, T, P; scanf("%d%d%d",&S,&T,&P);
		int x = P;
		if(S <= T) go(S, T, x);
		else {
			go(S, N, x);
			go(1, T, x);
		}
		printf("%d\n", x);
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; 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",&X[i]);
   ~~~~~^~~~~~~~~~~~
sushi.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int S, T, P; scanf("%d%d%d",&S,&T,&P);
                ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 504 KB Output is correct
2 Correct 58 ms 504 KB Output is correct
3 Correct 58 ms 504 KB Output is correct
4 Correct 58 ms 504 KB Output is correct
5 Correct 57 ms 604 KB Output is correct
6 Correct 59 ms 632 KB Output is correct
7 Correct 50 ms 464 KB Output is correct
8 Correct 49 ms 376 KB Output is correct
9 Correct 60 ms 504 KB Output is correct
10 Correct 59 ms 504 KB Output is correct
11 Correct 68 ms 536 KB Output is correct
12 Correct 69 ms 504 KB Output is correct
13 Correct 77 ms 504 KB Output is correct
14 Correct 64 ms 504 KB Output is correct
15 Correct 66 ms 504 KB Output is correct
16 Correct 30 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 3 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 3526 ms 79440 KB Output is correct
2 Correct 3520 ms 78996 KB Output is correct
3 Correct 1939 ms 78368 KB Output is correct
4 Correct 3510 ms 79076 KB Output is correct
5 Correct 2911 ms 79160 KB Output is correct
6 Correct 3576 ms 79108 KB Output is correct
7 Correct 3694 ms 79228 KB Output is correct
8 Correct 3584 ms 79044 KB Output is correct
9 Correct 1775 ms 78352 KB Output is correct
10 Correct 2894 ms 79200 KB Output is correct
11 Correct 1719 ms 78436 KB Output is correct
12 Correct 2911 ms 79428 KB Output is correct
13 Correct 3488 ms 79368 KB Output is correct
14 Correct 3521 ms 79220 KB Output is correct
15 Correct 1834 ms 78456 KB Output is correct
16 Correct 3637 ms 79276 KB Output is correct
17 Correct 3044 ms 79284 KB Output is correct
18 Correct 3519 ms 79276 KB Output is correct
19 Correct 3585 ms 79380 KB Output is correct
20 Correct 3538 ms 79532 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 504 KB Output is correct
2 Correct 58 ms 504 KB Output is correct
3 Correct 58 ms 504 KB Output is correct
4 Correct 58 ms 504 KB Output is correct
5 Correct 57 ms 604 KB Output is correct
6 Correct 59 ms 632 KB Output is correct
7 Correct 50 ms 464 KB Output is correct
8 Correct 49 ms 376 KB Output is correct
9 Correct 60 ms 504 KB Output is correct
10 Correct 59 ms 504 KB Output is correct
11 Correct 68 ms 536 KB Output is correct
12 Correct 69 ms 504 KB Output is correct
13 Correct 77 ms 504 KB Output is correct
14 Correct 64 ms 504 KB Output is correct
15 Correct 66 ms 504 KB Output is correct
16 Correct 30 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 3 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 3526 ms 79440 KB Output is correct
24 Correct 3520 ms 78996 KB Output is correct
25 Correct 1939 ms 78368 KB Output is correct
26 Correct 3510 ms 79076 KB Output is correct
27 Correct 2911 ms 79160 KB Output is correct
28 Correct 3576 ms 79108 KB Output is correct
29 Correct 3694 ms 79228 KB Output is correct
30 Correct 3584 ms 79044 KB Output is correct
31 Correct 1775 ms 78352 KB Output is correct
32 Correct 2894 ms 79200 KB Output is correct
33 Correct 1719 ms 78436 KB Output is correct
34 Correct 2911 ms 79428 KB Output is correct
35 Correct 3488 ms 79368 KB Output is correct
36 Correct 3521 ms 79220 KB Output is correct
37 Correct 1834 ms 78456 KB Output is correct
38 Correct 3637 ms 79276 KB Output is correct
39 Correct 3044 ms 79284 KB Output is correct
40 Correct 3519 ms 79276 KB Output is correct
41 Correct 3585 ms 79380 KB Output is correct
42 Correct 3538 ms 79532 KB Output is correct
43 Correct 3004 ms 12492 KB Output is correct
44 Correct 2954 ms 12280 KB Output is correct
45 Correct 2367 ms 8940 KB Output is correct
46 Correct 2967 ms 12448 KB Output is correct
47 Correct 2985 ms 12540 KB Output is correct
48 Correct 3609 ms 12544 KB Output is correct
49 Correct 3799 ms 12576 KB Output is correct
50 Correct 3802 ms 12492 KB Output is correct
51 Correct 3869 ms 12584 KB Output is correct
52 Correct 3823 ms 19032 KB Output is correct
53 Correct 3669 ms 18252 KB Output is correct
54 Correct 4236 ms 18548 KB Output is correct
55 Correct 4506 ms 18312 KB Output is correct
56 Correct 4570 ms 18152 KB Output is correct
57 Correct 4509 ms 18412 KB Output is correct
58 Correct 2738 ms 14136 KB Output is correct
59 Correct 2782 ms 14404 KB Output is correct
60 Correct 3847 ms 82316 KB Output is correct
61 Correct 4500 ms 82116 KB Output is correct
62 Correct 4488 ms 82064 KB Output is correct
63 Correct 4448 ms 82012 KB Output is correct
64 Correct 1732 ms 8832 KB Output is correct
65 Correct 2001 ms 45052 KB Output is correct
66 Correct 2017 ms 45084 KB Output is correct
67 Correct 3870 ms 68792 KB Output is correct
68 Correct 4078 ms 68676 KB Output is correct
69 Correct 4067 ms 68616 KB Output is correct
70 Correct 4051 ms 68568 KB Output is correct