답안 #654268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654268	2022-10-30T18:17:36 Z	thiago_bastos	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	753 ms	55580 KB

sortbooks

#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
 
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;	

void solve() {
	int n, m;
	vector<ii> in;
	set<ii> out;

	cin >> n >> m;

	vector<int> w(n);
	vector<bool> can(m, false);

	for(int& v : w) cin >> v;

	vector<tuple<int, int, int, int>> query(m);

	for(int i = 0; i < m; ++i) {
		int l, r, k;
		cin >> l >> r >> k;
		--l, --r;
		query[i] = {r, l, k, i};
	}

	sort(all(query));

	for(int i = 0, j = 0; i < n; ++i) {
		vector<ii> tmp;

		while(!in.empty() && in.back().sc <= w[i]) {
			tmp.pb(in.back());
			in.pop_back();
		}

		reverse(all(tmp));

		for(int j = 0; j < (int)tmp.size() - 1; ++j) {
			tmp[j].sc += tmp[j + 1].sc;
			if(auto it = out.lower_bound(ii(tmp[j].fi, -1)); it == out.end() || tmp[j].sc > it->sc) {
				it = out.insert(tmp[j]).fi;
				while(it != out.begin() && prev(it)->sc <= it->sc) it = out.erase(prev(it));
			}
		}

		in.pb({i, w[i]});

		while(j < m && get<0>(query[j]) == i) {
			auto [r, l, k, pos] = query[j++];

			auto i1 = lower_bound(all(in), ii(l, -1));

			int mood = 0;

			if(in.end() - i1 >= 2) mood = i1->sc + next(i1)->sc;
			
			auto i2 = out.lower_bound(ii(l, -1));

			if(i2 != out.end()) mood = max(mood, i2->sc);

			can[pos] = mood <= k;
		}
	}

	for(bool x : can) cout << x << '\n';
}	

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
 //	cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	4 ms	460 KB	Output is correct
13	Correct	5 ms	468 KB	Output is correct
14	Correct	4 ms	580 KB	Output is correct
15	Correct	4 ms	456 KB	Output is correct
16	Correct	4 ms	468 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	460 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	658 ms	21940 KB	Output is correct
2	Correct	697 ms	22008 KB	Output is correct
3	Correct	692 ms	54656 KB	Output is correct
4	Correct	687 ms	54816 KB	Output is correct
5	Correct	612 ms	54828 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	2672 KB	Output is correct
2	Correct	61 ms	4364 KB	Output is correct
3	Correct	51 ms	4428 KB	Output is correct
4	Correct	52 ms	4460 KB	Output is correct
5	Correct	47 ms	4440 KB	Output is correct
6	Correct	52 ms	4308 KB	Output is correct
7	Correct	51 ms	4316 KB	Output is correct
8	Correct	51 ms	4124 KB	Output is correct
9	Correct	42 ms	3408 KB	Output is correct
10	Correct	48 ms	4060 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	4 ms	460 KB	Output is correct
13	Correct	5 ms	468 KB	Output is correct
14	Correct	4 ms	580 KB	Output is correct
15	Correct	4 ms	456 KB	Output is correct
16	Correct	4 ms	468 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	460 KB	Output is correct
19	Correct	144 ms	11124 KB	Output is correct
20	Correct	142 ms	11212 KB	Output is correct
21	Correct	143 ms	11144 KB	Output is correct
22	Correct	155 ms	11024 KB	Output is correct
23	Correct	142 ms	11068 KB	Output is correct
24	Correct	116 ms	10896 KB	Output is correct
25	Correct	125 ms	10968 KB	Output is correct
26	Correct	124 ms	11088 KB	Output is correct
27	Correct	130 ms	11224 KB	Output is correct
28	Correct	141 ms	11152 KB	Output is correct
29	Correct	119 ms	11368 KB	Output is correct
30	Correct	129 ms	11152 KB	Output is correct
31	Correct	149 ms	11212 KB	Output is correct
32	Correct	117 ms	11228 KB	Output is correct
33	Correct	141 ms	11152 KB	Output is correct
34	Correct	126 ms	10852 KB	Output is correct
35	Correct	139 ms	10900 KB	Output is correct
36	Correct	118 ms	10708 KB	Output is correct
37	Correct	118 ms	10624 KB	Output is correct
38	Correct	120 ms	10828 KB	Output is correct
39	Correct	133 ms	9796 KB	Output is correct
40	Correct	98 ms	8848 KB	Output is correct
41	Correct	107 ms	9292 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	4 ms	460 KB	Output is correct
13	Correct	5 ms	468 KB	Output is correct
14	Correct	4 ms	580 KB	Output is correct
15	Correct	4 ms	456 KB	Output is correct
16	Correct	4 ms	468 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	460 KB	Output is correct
19	Correct	658 ms	21940 KB	Output is correct
20	Correct	697 ms	22008 KB	Output is correct
21	Correct	692 ms	54656 KB	Output is correct
22	Correct	687 ms	54816 KB	Output is correct
23	Correct	612 ms	54828 KB	Output is correct
24	Correct	58 ms	2672 KB	Output is correct
25	Correct	61 ms	4364 KB	Output is correct
26	Correct	51 ms	4428 KB	Output is correct
27	Correct	52 ms	4460 KB	Output is correct
28	Correct	47 ms	4440 KB	Output is correct
29	Correct	52 ms	4308 KB	Output is correct
30	Correct	51 ms	4316 KB	Output is correct
31	Correct	51 ms	4124 KB	Output is correct
32	Correct	42 ms	3408 KB	Output is correct
33	Correct	48 ms	4060 KB	Output is correct
34	Correct	144 ms	11124 KB	Output is correct
35	Correct	142 ms	11212 KB	Output is correct
36	Correct	143 ms	11144 KB	Output is correct
37	Correct	155 ms	11024 KB	Output is correct
38	Correct	142 ms	11068 KB	Output is correct
39	Correct	116 ms	10896 KB	Output is correct
40	Correct	125 ms	10968 KB	Output is correct
41	Correct	124 ms	11088 KB	Output is correct
42	Correct	130 ms	11224 KB	Output is correct
43	Correct	141 ms	11152 KB	Output is correct
44	Correct	119 ms	11368 KB	Output is correct
45	Correct	129 ms	11152 KB	Output is correct
46	Correct	149 ms	11212 KB	Output is correct
47	Correct	117 ms	11228 KB	Output is correct
48	Correct	141 ms	11152 KB	Output is correct
49	Correct	126 ms	10852 KB	Output is correct
50	Correct	139 ms	10900 KB	Output is correct
51	Correct	118 ms	10708 KB	Output is correct
52	Correct	118 ms	10624 KB	Output is correct
53	Correct	120 ms	10828 KB	Output is correct
54	Correct	133 ms	9796 KB	Output is correct
55	Correct	98 ms	8848 KB	Output is correct
56	Correct	107 ms	9292 KB	Output is correct
57	Correct	717 ms	55528 KB	Output is correct
58	Correct	717 ms	55500 KB	Output is correct
59	Correct	716 ms	55356 KB	Output is correct
60	Correct	705 ms	55364 KB	Output is correct
61	Correct	714 ms	55372 KB	Output is correct
62	Correct	753 ms	55580 KB	Output is correct
63	Correct	662 ms	53540 KB	Output is correct
64	Correct	613 ms	53504 KB	Output is correct
65	Correct	640 ms	55576 KB	Output is correct
66	Correct	634 ms	55464 KB	Output is correct
67	Correct	613 ms	55496 KB	Output is correct
68	Correct	624 ms	55556 KB	Output is correct
69	Correct	612 ms	55540 KB	Output is correct
70	Correct	631 ms	55448 KB	Output is correct
71	Correct	619 ms	55432 KB	Output is correct
72	Correct	610 ms	55480 KB	Output is correct
73	Correct	639 ms	51988 KB	Output is correct
74	Correct	628 ms	53100 KB	Output is correct
75	Correct	595 ms	52112 KB	Output is correct
76	Correct	596 ms	51996 KB	Output is correct
77	Correct	631 ms	51992 KB	Output is correct
78	Correct	619 ms	49308 KB	Output is correct
79	Correct	526 ms	42684 KB	Output is correct
80	Correct	617 ms	46500 KB	Output is correct

답안 #654268

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 9.0 / 9.0

Subtask #3 13.0 / 13.0

Subtask #4 17.0 / 17.0

Subtask #5 30.0 / 30.0

Subtask #6 23.0 / 23.0

Subtask #1
8.0 / 8.0

Subtask #2
9.0 / 9.0

Subtask #3
13.0 / 13.0

Subtask #4
17.0 / 17.0

Subtask #5
30.0 / 30.0

Subtask #6
23.0 / 23.0