답안 #237548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237548	2020-06-07T08:45:07 Z	kostia244	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1018 ms	80532 KB

sortbooks

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<20;
int n, m, a[maxn], f[maxn], ans[maxn];
vector<array<int, 3>> q[maxn];
void upd(int i, int x) {
	for(;i; i -= i&-i) f[i] = max(f[i], x); 
}
int get(int i) {
	int r = 0;
	for(;i <= n; i += i&-i) r = max(f[i], r);
	return r; 
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	a[0] = 1<<30;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int l, r, k, i = 0; i < m; i++) {
		cin >> l >> r >> k;
		q[r].push_back({l, k, i});
	}
	vector<int> t {0};
	for(int i = 1; i <= n; i++) {
		while(a[t.back()] <= a[i]) t.pop_back();
		if(t.back()) upd(t.back(), a[t.back()] + a[i]);
		t.push_back(i);
		for(auto [l, k, p] : q[i]) ans[p] = get(l) <= k;
	}
	for(int i = 0; i < m; i++) cout << ans[i] << '\n';
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	24960 KB	Output is correct
2	Correct	19 ms	24960 KB	Output is correct
3	Correct	19 ms	24960 KB	Output is correct
4	Correct	19 ms	24960 KB	Output is correct
5	Correct	19 ms	24960 KB	Output is correct
6	Correct	19 ms	24960 KB	Output is correct
7	Correct	22 ms	25088 KB	Output is correct
8	Correct	19 ms	25088 KB	Output is correct
9	Correct	19 ms	24960 KB	Output is correct
10	Correct	19 ms	25216 KB	Output is correct
11	Correct	21 ms	25088 KB	Output is correct
12	Correct	22 ms	25192 KB	Output is correct
13	Correct	22 ms	25216 KB	Output is correct
14	Correct	23 ms	25344 KB	Output is correct
15	Correct	23 ms	25344 KB	Output is correct
16	Correct	22 ms	25216 KB	Output is correct
17	Correct	21 ms	25216 KB	Output is correct
18	Correct	23 ms	25216 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1006 ms	60512 KB	Output is correct
2	Correct	1006 ms	60588 KB	Output is correct
3	Correct	1014 ms	60664 KB	Output is correct
4	Correct	1018 ms	60672 KB	Output is correct
5	Correct	953 ms	56568 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	28536 KB	Output is correct
2	Correct	73 ms	30200 KB	Output is correct
3	Correct	83 ms	30072 KB	Output is correct
4	Correct	78 ms	30072 KB	Output is correct
5	Correct	79 ms	30072 KB	Output is correct
6	Correct	67 ms	29432 KB	Output is correct
7	Correct	67 ms	29560 KB	Output is correct
8	Correct	79 ms	29616 KB	Output is correct
9	Correct	59 ms	28336 KB	Output is correct
10	Correct	76 ms	29616 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	24960 KB	Output is correct
2	Correct	19 ms	24960 KB	Output is correct
3	Correct	19 ms	24960 KB	Output is correct
4	Correct	19 ms	24960 KB	Output is correct
5	Correct	19 ms	24960 KB	Output is correct
6	Correct	19 ms	24960 KB	Output is correct
7	Correct	22 ms	25088 KB	Output is correct
8	Correct	19 ms	25088 KB	Output is correct
9	Correct	19 ms	24960 KB	Output is correct
10	Correct	19 ms	25216 KB	Output is correct
11	Correct	21 ms	25088 KB	Output is correct
12	Correct	22 ms	25192 KB	Output is correct
13	Correct	22 ms	25216 KB	Output is correct
14	Correct	23 ms	25344 KB	Output is correct
15	Correct	23 ms	25344 KB	Output is correct
16	Correct	22 ms	25216 KB	Output is correct
17	Correct	21 ms	25216 KB	Output is correct
18	Correct	23 ms	25216 KB	Output is correct
19	Correct	191 ms	36472 KB	Output is correct
20	Correct	194 ms	36600 KB	Output is correct
21	Correct	166 ms	36092 KB	Output is correct
22	Correct	157 ms	35960 KB	Output is correct
23	Correct	159 ms	36088 KB	Output is correct
24	Correct	146 ms	35064 KB	Output is correct
25	Correct	149 ms	35064 KB	Output is correct
26	Correct	167 ms	35320 KB	Output is correct
27	Correct	161 ms	35296 KB	Output is correct
28	Correct	181 ms	35576 KB	Output is correct
29	Correct	176 ms	35704 KB	Output is correct
30	Correct	182 ms	35708 KB	Output is correct
31	Correct	174 ms	35816 KB	Output is correct
32	Correct	179 ms	35704 KB	Output is correct
33	Correct	181 ms	35688 KB	Output is correct
34	Correct	145 ms	34808 KB	Output is correct
35	Correct	141 ms	34680 KB	Output is correct
36	Correct	145 ms	34680 KB	Output is correct
37	Correct	141 ms	34552 KB	Output is correct
38	Correct	147 ms	34576 KB	Output is correct
39	Correct	165 ms	35504 KB	Output is correct
40	Correct	143 ms	34600 KB	Output is correct
41	Correct	155 ms	35372 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	24960 KB	Output is correct
2	Correct	19 ms	24960 KB	Output is correct
3	Correct	19 ms	24960 KB	Output is correct
4	Correct	19 ms	24960 KB	Output is correct
5	Correct	19 ms	24960 KB	Output is correct
6	Correct	19 ms	24960 KB	Output is correct
7	Correct	22 ms	25088 KB	Output is correct
8	Correct	19 ms	25088 KB	Output is correct
9	Correct	19 ms	24960 KB	Output is correct
10	Correct	19 ms	25216 KB	Output is correct
11	Correct	21 ms	25088 KB	Output is correct
12	Correct	22 ms	25192 KB	Output is correct
13	Correct	22 ms	25216 KB	Output is correct
14	Correct	23 ms	25344 KB	Output is correct
15	Correct	23 ms	25344 KB	Output is correct
16	Correct	22 ms	25216 KB	Output is correct
17	Correct	21 ms	25216 KB	Output is correct
18	Correct	23 ms	25216 KB	Output is correct
19	Correct	1006 ms	60512 KB	Output is correct
20	Correct	1006 ms	60588 KB	Output is correct
21	Correct	1014 ms	60664 KB	Output is correct
22	Correct	1018 ms	60672 KB	Output is correct
23	Correct	953 ms	56568 KB	Output is correct
24	Correct	80 ms	28536 KB	Output is correct
25	Correct	73 ms	30200 KB	Output is correct
26	Correct	83 ms	30072 KB	Output is correct
27	Correct	78 ms	30072 KB	Output is correct
28	Correct	79 ms	30072 KB	Output is correct
29	Correct	67 ms	29432 KB	Output is correct
30	Correct	67 ms	29560 KB	Output is correct
31	Correct	79 ms	29616 KB	Output is correct
32	Correct	59 ms	28336 KB	Output is correct
33	Correct	76 ms	29616 KB	Output is correct
34	Correct	191 ms	36472 KB	Output is correct
35	Correct	194 ms	36600 KB	Output is correct
36	Correct	166 ms	36092 KB	Output is correct
37	Correct	157 ms	35960 KB	Output is correct
38	Correct	159 ms	36088 KB	Output is correct
39	Correct	146 ms	35064 KB	Output is correct
40	Correct	149 ms	35064 KB	Output is correct
41	Correct	167 ms	35320 KB	Output is correct
42	Correct	161 ms	35296 KB	Output is correct
43	Correct	181 ms	35576 KB	Output is correct
44	Correct	176 ms	35704 KB	Output is correct
45	Correct	182 ms	35708 KB	Output is correct
46	Correct	174 ms	35816 KB	Output is correct
47	Correct	179 ms	35704 KB	Output is correct
48	Correct	181 ms	35688 KB	Output is correct
49	Correct	145 ms	34808 KB	Output is correct
50	Correct	141 ms	34680 KB	Output is correct
51	Correct	145 ms	34680 KB	Output is correct
52	Correct	141 ms	34552 KB	Output is correct
53	Correct	147 ms	34576 KB	Output is correct
54	Correct	165 ms	35504 KB	Output is correct
55	Correct	143 ms	34600 KB	Output is correct
56	Correct	155 ms	35372 KB	Output is correct
57	Correct	991 ms	72312 KB	Output is correct
58	Correct	993 ms	72184 KB	Output is correct
59	Correct	930 ms	70652 KB	Output is correct
60	Correct	962 ms	70640 KB	Output is correct
61	Correct	935 ms	70776 KB	Output is correct
62	Correct	943 ms	70708 KB	Output is correct
63	Correct	660 ms	64324 KB	Output is correct
64	Correct	665 ms	64096 KB	Output is correct
65	Correct	900 ms	66768 KB	Output is correct
66	Correct	883 ms	66552 KB	Output is correct
67	Correct	901 ms	66644 KB	Output is correct
68	Correct	937 ms	68404 KB	Output is correct
69	Correct	975 ms	68256 KB	Output is correct
70	Correct	952 ms	68028 KB	Output is correct
71	Correct	948 ms	67960 KB	Output is correct
72	Correct	951 ms	67784 KB	Output is correct
73	Correct	620 ms	75276 KB	Output is correct
74	Correct	639 ms	54904 KB	Output is correct
75	Correct	635 ms	80532 KB	Output is correct
76	Correct	642 ms	62104 KB	Output is correct
77	Correct	628 ms	61976 KB	Output is correct
78	Correct	895 ms	66676 KB	Output is correct
79	Correct	743 ms	72816 KB	Output is correct
80	Correct	845 ms	78960 KB	Output is correct

답안 #237548

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