oj.uz

Submission #55953

# Submission time Handle Problem Language Result Execution time Memory
55953 2018-07-09T08:14:34 Z 김현수(#2092) Sushi (JOI16_sushi) C++11
100 / 100
 8219 ms 97616 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 400005, BS = 500;

int n, q, bc, a[N];

struct bucket {
	vector<int> v;
	priority_queue<int> p, d;
	void ins (int V) {
		v.push_back(V);
		p.push(V);
	}
	void relax () {
		for(int i=0;i<(int)v.size();i++) {
			d.push(-v[i]);
			v[i] = -d.top();
			d.pop();
		}
		while(!d.empty()) {
			d.pop();
		}
	}
	int put (int X) {
		p.push(X);
		d.push(-X);
		int T = p.top();
		p.pop();
		return T;
	}
	int naive (int S, int E, int X) {
		if(E == -1) E = (int)v.size() - 1;
		relax();
		for(int i=S;i<=E;i++) {
			if(v[i] > X) swap(v[i], X);
		}
		while(!p.empty()) {
			p.pop();
		}
		for(int i=0;i<(int)v.size();i++) {
			p.push(v[i]);
		}
		return X;
	}
} b[N/BS+5];

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;i++) {
		scanf("%d",&a[i]);
		b[i/BS].ins(a[i]);
	}
	bc = (n-1)/BS + 1;
	while(q--) {
		int A, B, C;
		scanf("%d%d%d",&A,&B,&C);
		A--;
		B--;
		if(A <= B && A/BS == B/BS) {
			printf("%d\n",b[A/BS].naive(A%BS, B%BS, C));
		}
		else {
			C = b[A/BS].naive(A%BS, -1, C);
			for(int i=A/BS;;) {
				i = (i+1) % bc;
				if(i == B/BS) break;
				else C = b[i].put(C);
			}
			printf("%d\n",b[B/BS].naive(0, B%BS, C));
		}
	}
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:50: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:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
telegraph.cpp:58: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 184 ms 500 KB Output is correct
2 Correct 197 ms 768 KB Output is correct
3 Correct 192 ms 768 KB Output is correct
4 Correct 210 ms 772 KB Output is correct
5 Correct 205 ms 772 KB Output is correct
6 Correct 204 ms 772 KB Output is correct
7 Correct 102 ms 772 KB Output is correct
8 Correct 101 ms 836 KB Output is correct
9 Correct 201 ms 836 KB Output is correct
10 Correct 198 ms 836 KB Output is correct
11 Correct 217 ms 836 KB Output is correct
12 Correct 194 ms 836 KB Output is correct
13 Correct 199 ms 836 KB Output is correct
14 Correct 215 ms 880 KB Output is correct
15 Correct 213 ms 908 KB Output is correct
16 Correct 94 ms 908 KB Output is correct
17 Correct 3 ms 908 KB Output is correct
18 Correct 2 ms 908 KB Output is correct
19 Correct 2 ms 908 KB Output is correct
20 Correct 2 ms 908 KB Output is correct
21 Correct 2 ms 908 KB Output is correct
22 Correct 2 ms 908 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7217 ms 97488 KB Output is correct
2 Correct 7245 ms 97496 KB Output is correct
3 Correct 3399 ms 97496 KB Output is correct
4 Correct 7192 ms 97532 KB Output is correct
5 Correct 6199 ms 97532 KB Output is correct
6 Correct 7295 ms 97532 KB Output is correct
7 Correct 7481 ms 97536 KB Output is correct
8 Correct 7262 ms 97536 KB Output is correct
9 Correct 2939 ms 97536 KB Output is correct
10 Correct 6098 ms 97536 KB Output is correct
11 Correct 3014 ms 97536 KB Output is correct
12 Correct 6334 ms 97536 KB Output is correct
13 Correct 6954 ms 97536 KB Output is correct
14 Correct 7065 ms 97536 KB Output is correct
15 Correct 3630 ms 97536 KB Output is correct
16 Correct 7366 ms 97584 KB Output is correct
17 Correct 6236 ms 97588 KB Output is correct
18 Correct 6855 ms 97588 KB Output is correct
19 Correct 7165 ms 97588 KB Output is correct
20 Correct 7138 ms 97616 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 500 KB Output is correct
2 Correct 197 ms 768 KB Output is correct
3 Correct 192 ms 768 KB Output is correct
4 Correct 210 ms 772 KB Output is correct
5 Correct 205 ms 772 KB Output is correct
6 Correct 204 ms 772 KB Output is correct
7 Correct 102 ms 772 KB Output is correct
8 Correct 101 ms 836 KB Output is correct
9 Correct 201 ms 836 KB Output is correct
10 Correct 198 ms 836 KB Output is correct
11 Correct 217 ms 836 KB Output is correct
12 Correct 194 ms 836 KB Output is correct
13 Correct 199 ms 836 KB Output is correct
14 Correct 215 ms 880 KB Output is correct
15 Correct 213 ms 908 KB Output is correct
16 Correct 94 ms 908 KB Output is correct
17 Correct 3 ms 908 KB Output is correct
18 Correct 2 ms 908 KB Output is correct
19 Correct 2 ms 908 KB Output is correct
20 Correct 2 ms 908 KB Output is correct
21 Correct 2 ms 908 KB Output is correct
22 Correct 2 ms 908 KB Output is correct
23 Correct 7217 ms 97488 KB Output is correct
24 Correct 7245 ms 97496 KB Output is correct
25 Correct 3399 ms 97496 KB Output is correct
26 Correct 7192 ms 97532 KB Output is correct
27 Correct 6199 ms 97532 KB Output is correct
28 Correct 7295 ms 97532 KB Output is correct
29 Correct 7481 ms 97536 KB Output is correct
30 Correct 7262 ms 97536 KB Output is correct
31 Correct 2939 ms 97536 KB Output is correct
32 Correct 6098 ms 97536 KB Output is correct
33 Correct 3014 ms 97536 KB Output is correct
34 Correct 6334 ms 97536 KB Output is correct
35 Correct 6954 ms 97536 KB Output is correct
36 Correct 7065 ms 97536 KB Output is correct
37 Correct 3630 ms 97536 KB Output is correct
38 Correct 7366 ms 97584 KB Output is correct
39 Correct 6236 ms 97588 KB Output is correct
40 Correct 6855 ms 97588 KB Output is correct
41 Correct 7165 ms 97588 KB Output is correct
42 Correct 7138 ms 97616 KB Output is correct
43 Correct 5672 ms 97616 KB Output is correct
44 Correct 5139 ms 97616 KB Output is correct
45 Correct 3269 ms 97616 KB Output is correct
46 Correct 5469 ms 97616 KB Output is correct
47 Correct 5080 ms 97616 KB Output is correct
48 Correct 5835 ms 97616 KB Output is correct
49 Correct 6012 ms 97616 KB Output is correct
50 Correct 6032 ms 97616 KB Output is correct
51 Correct 6188 ms 97616 KB Output is correct
52 Correct 7627 ms 97616 KB Output is correct
53 Correct 7326 ms 97616 KB Output is correct
54 Correct 7032 ms 97616 KB Output is correct
55 Correct 8145 ms 97616 KB Output is correct
56 Correct 7794 ms 97616 KB Output is correct
57 Correct 8219 ms 97616 KB Output is correct
58 Correct 5183 ms 97616 KB Output is correct
59 Correct 5161 ms 97616 KB Output is correct
60 Correct 5649 ms 97616 KB Output is correct
61 Correct 7170 ms 97616 KB Output is correct
62 Correct 7467 ms 97616 KB Output is correct
63 Correct 6653 ms 97616 KB Output is correct
64 Correct 2400 ms 97616 KB Output is correct
65 Correct 3639 ms 97616 KB Output is correct
66 Correct 3777 ms 97616 KB Output is correct
67 Correct 6478 ms 97616 KB Output is correct
68 Correct 7380 ms 97616 KB Output is correct
69 Correct 7387 ms 97616 KB Output is correct
70 Correct 7229 ms 97616 KB Output is correct