답안 #55979 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55979	2018-07-09T08:51:24 Z	khsoo01	Sushi (JOI16_sushi)	C++11	100 / 100	8977 ms	97696 KB

sushi

#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

#	결과	실행 시간	메모리	Grader output
1	Correct	237 ms	508 KB	Output is correct
2	Correct	254 ms	612 KB	Output is correct
3	Correct	242 ms	692 KB	Output is correct
4	Correct	253 ms	756 KB	Output is correct
5	Correct	207 ms	756 KB	Output is correct
6	Correct	240 ms	756 KB	Output is correct
7	Correct	114 ms	756 KB	Output is correct
8	Correct	122 ms	756 KB	Output is correct
9	Correct	244 ms	768 KB	Output is correct
10	Correct	234 ms	808 KB	Output is correct
11	Correct	215 ms	840 KB	Output is correct
12	Correct	206 ms	848 KB	Output is correct
13	Correct	221 ms	848 KB	Output is correct
14	Correct	228 ms	848 KB	Output is correct
15	Correct	222 ms	848 KB	Output is correct
16	Correct	98 ms	848 KB	Output is correct
17	Correct	2 ms	848 KB	Output is correct
18	Correct	3 ms	848 KB	Output is correct
19	Correct	3 ms	848 KB	Output is correct
20	Correct	3 ms	848 KB	Output is correct
21	Correct	2 ms	848 KB	Output is correct
22	Correct	2 ms	848 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8695 ms	97460 KB	Output is correct
2	Correct	8953 ms	97460 KB	Output is correct
3	Correct	4127 ms	97460 KB	Output is correct
4	Correct	8977 ms	97460 KB	Output is correct
5	Correct	7849 ms	97460 KB	Output is correct
6	Correct	8609 ms	97528 KB	Output is correct
7	Correct	8508 ms	97696 KB	Output is correct
8	Correct	8284 ms	97696 KB	Output is correct
9	Correct	3692 ms	97696 KB	Output is correct
10	Correct	7744 ms	97696 KB	Output is correct
11	Correct	3724 ms	97696 KB	Output is correct
12	Correct	7622 ms	97696 KB	Output is correct
13	Correct	8697 ms	97696 KB	Output is correct
14	Correct	8532 ms	97696 KB	Output is correct
15	Correct	4217 ms	97696 KB	Output is correct
16	Correct	8613 ms	97696 KB	Output is correct
17	Correct	7555 ms	97696 KB	Output is correct
18	Correct	8977 ms	97696 KB	Output is correct
19	Correct	7777 ms	97696 KB	Output is correct
20	Correct	6968 ms	97696 KB	Output is correct

Subtask #3
80.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	237 ms	508 KB	Output is correct
2	Correct	254 ms	612 KB	Output is correct
3	Correct	242 ms	692 KB	Output is correct
4	Correct	253 ms	756 KB	Output is correct
5	Correct	207 ms	756 KB	Output is correct
6	Correct	240 ms	756 KB	Output is correct
7	Correct	114 ms	756 KB	Output is correct
8	Correct	122 ms	756 KB	Output is correct
9	Correct	244 ms	768 KB	Output is correct
10	Correct	234 ms	808 KB	Output is correct
11	Correct	215 ms	840 KB	Output is correct
12	Correct	206 ms	848 KB	Output is correct
13	Correct	221 ms	848 KB	Output is correct
14	Correct	228 ms	848 KB	Output is correct
15	Correct	222 ms	848 KB	Output is correct
16	Correct	98 ms	848 KB	Output is correct
17	Correct	2 ms	848 KB	Output is correct
18	Correct	3 ms	848 KB	Output is correct
19	Correct	3 ms	848 KB	Output is correct
20	Correct	3 ms	848 KB	Output is correct
21	Correct	2 ms	848 KB	Output is correct
22	Correct	2 ms	848 KB	Output is correct
23	Correct	8695 ms	97460 KB	Output is correct
24	Correct	8953 ms	97460 KB	Output is correct
25	Correct	4127 ms	97460 KB	Output is correct
26	Correct	8977 ms	97460 KB	Output is correct
27	Correct	7849 ms	97460 KB	Output is correct
28	Correct	8609 ms	97528 KB	Output is correct
29	Correct	8508 ms	97696 KB	Output is correct
30	Correct	8284 ms	97696 KB	Output is correct
31	Correct	3692 ms	97696 KB	Output is correct
32	Correct	7744 ms	97696 KB	Output is correct
33	Correct	3724 ms	97696 KB	Output is correct
34	Correct	7622 ms	97696 KB	Output is correct
35	Correct	8697 ms	97696 KB	Output is correct
36	Correct	8532 ms	97696 KB	Output is correct
37	Correct	4217 ms	97696 KB	Output is correct
38	Correct	8613 ms	97696 KB	Output is correct
39	Correct	7555 ms	97696 KB	Output is correct
40	Correct	8977 ms	97696 KB	Output is correct
41	Correct	7777 ms	97696 KB	Output is correct
42	Correct	6968 ms	97696 KB	Output is correct
43	Correct	5152 ms	97696 KB	Output is correct
44	Correct	5267 ms	97696 KB	Output is correct
45	Correct	3650 ms	97696 KB	Output is correct
46	Correct	5026 ms	97696 KB	Output is correct
47	Correct	5017 ms	97696 KB	Output is correct
48	Correct	5430 ms	97696 KB	Output is correct
49	Correct	5937 ms	97696 KB	Output is correct
50	Correct	5640 ms	97696 KB	Output is correct
51	Correct	6171 ms	97696 KB	Output is correct
52	Correct	7458 ms	97696 KB	Output is correct
53	Correct	7132 ms	97696 KB	Output is correct
54	Correct	8122 ms	97696 KB	Output is correct
55	Correct	7750 ms	97696 KB	Output is correct
56	Correct	7015 ms	97696 KB	Output is correct
57	Correct	7070 ms	97696 KB	Output is correct
58	Correct	4906 ms	97696 KB	Output is correct
59	Correct	5300 ms	97696 KB	Output is correct
60	Correct	5923 ms	97696 KB	Output is correct
61	Correct	6789 ms	97696 KB	Output is correct
62	Correct	6659 ms	97696 KB	Output is correct
63	Correct	6851 ms	97696 KB	Output is correct
64	Correct	2760 ms	97696 KB	Output is correct
65	Correct	4002 ms	97696 KB	Output is correct
66	Correct	3788 ms	97696 KB	Output is correct
67	Correct	7815 ms	97696 KB	Output is correct
68	Correct	8539 ms	97696 KB	Output is correct
69	Correct	8423 ms	97696 KB	Output is correct
70	Correct	8055 ms	97696 KB	Output is correct

답안 #55979

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