답안 #172127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172127	2019-12-31T08:10:52 Z	Nordway	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1634 ms	82552 KB

sortbooks

#include<bits/stdc++.h>

using namespace std;

struct edge {
	int l;
	int r;
	int k;
	int id;
};
bool cmp(edge l, edge r) {
 	return (l.r < r.r);
}
vector<int> t, a;  

void upd(int u, int l, int r, int pos, int val) {
 	if (r - l == 1) {
		t[u] = max(t[u], val);
		return;
 	}
 	int m = (l + r) / 2;
 	if (pos < m) upd(u + u + 1, l, m, pos, val);
 	else upd(u + u + 2, m, r, pos, val);
 	t[u] = max(t[u + u + 1], t[u + u + 2]);
}

int get(int u, int ul, int ur, int l, int r) {
 	if (ul >= r || l >= ur)
 		return 0;
 	if (l <= ul && ur <= r)
 		return t[u];
 	int um = (ul + ur) / 2;
 	return max(get(u + u + 1, ul, um, l, r), get(u + u + 2, um, ur, l, r));
}

int main() {
	ios_base::sync_with_stdio(NULL);
  	cin.tie(nullptr),cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<int> inv(n, -1), ans(m);
	t.resize(4 * n);
	a.resize(n);
	vector<edge> q(m);
	for (int& x : a)
		cin >> x;
	for (int i = 0; i < m; i++) {
	 	int l, r, x;
	 	cin >> l >> r >> x;
	 	l--, r--;
	 	q[i].l = l;
	 	q[i].r = r;
	 	q[i].id = i;
	 	q[i].k = x;
	}
	stack<int> s;
	for(int i = n - 1; i >= 0; i--){
  	 	while (!s.empty() && a[s.top()] < a[i]) {
  	 		inv[s.top()] = i;
  	 		s.pop();
  	 	}
  	 	s.push(i);	
  	}
	sort(q.begin(), q.end(), cmp);
	int pos = 0;
	for (int i = 0; i < n; i++) {
		if (inv[i] != -1) {
		 	upd(0, 0, n, inv[i], a[i] + a[inv[i]]);
		}
		while (pos < m && i == q[pos].r) {
			ans[q[pos].id] = (get(0, 0, n, q[pos].l, q[pos].r + 1) <= q[pos].k);
			pos++;
		}                	
	}
	for (int i = 0; i < m; i++)
		cout << ans[i] << "\n";
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	4 ms	504 KB	Output is correct
12	Correct	5 ms	632 KB	Output is correct
13	Correct	6 ms	632 KB	Output is correct
14	Correct	7 ms	680 KB	Output is correct
15	Correct	7 ms	760 KB	Output is correct
16	Correct	6 ms	760 KB	Output is correct
17	Correct	5 ms	632 KB	Output is correct
18	Correct	6 ms	632 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1533 ms	45380 KB	Output is correct
2	Correct	1634 ms	78408 KB	Output is correct
3	Correct	1586 ms	78200 KB	Output is correct
4	Correct	1537 ms	78400 KB	Output is correct
5	Correct	1298 ms	82552 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	4856 KB	Output is correct
2	Correct	114 ms	4868 KB	Output is correct
3	Correct	100 ms	7292 KB	Output is correct
4	Correct	118 ms	7288 KB	Output is correct
5	Correct	109 ms	7288 KB	Output is correct
6	Correct	90 ms	7104 KB	Output is correct
7	Correct	90 ms	7160 KB	Output is correct
8	Correct	94 ms	6776 KB	Output is correct
9	Correct	53 ms	3832 KB	Output is correct
10	Correct	92 ms	6736 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	4 ms	504 KB	Output is correct
12	Correct	5 ms	632 KB	Output is correct
13	Correct	6 ms	632 KB	Output is correct
14	Correct	7 ms	680 KB	Output is correct
15	Correct	7 ms	760 KB	Output is correct
16	Correct	6 ms	760 KB	Output is correct
17	Correct	5 ms	632 KB	Output is correct
18	Correct	6 ms	632 KB	Output is correct
19	Correct	273 ms	15916 KB	Output is correct
20	Correct	275 ms	15992 KB	Output is correct
21	Correct	255 ms	15864 KB	Output is correct
22	Correct	262 ms	15864 KB	Output is correct
23	Correct	258 ms	15864 KB	Output is correct
24	Correct	213 ms	16632 KB	Output is correct
25	Correct	213 ms	16504 KB	Output is correct
26	Correct	227 ms	16748 KB	Output is correct
27	Correct	221 ms	16632 KB	Output is correct
28	Correct	229 ms	16816 KB	Output is correct
29	Correct	233 ms	16748 KB	Output is correct
30	Correct	231 ms	16760 KB	Output is correct
31	Correct	235 ms	16888 KB	Output is correct
32	Correct	236 ms	16808 KB	Output is correct
33	Correct	245 ms	16888 KB	Output is correct
34	Correct	205 ms	16504 KB	Output is correct
35	Correct	205 ms	16504 KB	Output is correct
36	Correct	202 ms	16248 KB	Output is correct
37	Correct	211 ms	16348 KB	Output is correct
38	Correct	225 ms	16364 KB	Output is correct
39	Correct	211 ms	15076 KB	Output is correct
40	Correct	327 ms	12792 KB	Output is correct
41	Correct	217 ms	14456 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	4 ms	504 KB	Output is correct
12	Correct	5 ms	632 KB	Output is correct
13	Correct	6 ms	632 KB	Output is correct
14	Correct	7 ms	680 KB	Output is correct
15	Correct	7 ms	760 KB	Output is correct
16	Correct	6 ms	760 KB	Output is correct
17	Correct	5 ms	632 KB	Output is correct
18	Correct	6 ms	632 KB	Output is correct
19	Correct	1533 ms	45380 KB	Output is correct
20	Correct	1634 ms	78408 KB	Output is correct
21	Correct	1586 ms	78200 KB	Output is correct
22	Correct	1537 ms	78400 KB	Output is correct
23	Correct	1298 ms	82552 KB	Output is correct
24	Correct	115 ms	4856 KB	Output is correct
25	Correct	114 ms	4868 KB	Output is correct
26	Correct	100 ms	7292 KB	Output is correct
27	Correct	118 ms	7288 KB	Output is correct
28	Correct	109 ms	7288 KB	Output is correct
29	Correct	90 ms	7104 KB	Output is correct
30	Correct	90 ms	7160 KB	Output is correct
31	Correct	94 ms	6776 KB	Output is correct
32	Correct	53 ms	3832 KB	Output is correct
33	Correct	92 ms	6736 KB	Output is correct
34	Correct	273 ms	15916 KB	Output is correct
35	Correct	275 ms	15992 KB	Output is correct
36	Correct	255 ms	15864 KB	Output is correct
37	Correct	262 ms	15864 KB	Output is correct
38	Correct	258 ms	15864 KB	Output is correct
39	Correct	213 ms	16632 KB	Output is correct
40	Correct	213 ms	16504 KB	Output is correct
41	Correct	227 ms	16748 KB	Output is correct
42	Correct	221 ms	16632 KB	Output is correct
43	Correct	229 ms	16816 KB	Output is correct
44	Correct	233 ms	16748 KB	Output is correct
45	Correct	231 ms	16760 KB	Output is correct
46	Correct	235 ms	16888 KB	Output is correct
47	Correct	236 ms	16808 KB	Output is correct
48	Correct	245 ms	16888 KB	Output is correct
49	Correct	205 ms	16504 KB	Output is correct
50	Correct	205 ms	16504 KB	Output is correct
51	Correct	202 ms	16248 KB	Output is correct
52	Correct	211 ms	16348 KB	Output is correct
53	Correct	225 ms	16364 KB	Output is correct
54	Correct	211 ms	15076 KB	Output is correct
55	Correct	327 ms	12792 KB	Output is correct
56	Correct	217 ms	14456 KB	Output is correct
57	Correct	1566 ms	78844 KB	Output is correct
58	Correct	1573 ms	78900 KB	Output is correct
59	Correct	1532 ms	78860 KB	Output is correct
60	Correct	1566 ms	78616 KB	Output is correct
61	Correct	1540 ms	61444 KB	Output is correct
62	Correct	1525 ms	78468 KB	Output is correct
63	Correct	1154 ms	80836 KB	Output is correct
64	Correct	1186 ms	80280 KB	Output is correct
65	Correct	1317 ms	82048 KB	Output is correct
66	Correct	1303 ms	81808 KB	Output is correct
67	Correct	1322 ms	81508 KB	Output is correct
68	Correct	1356 ms	79996 KB	Output is correct
69	Correct	1352 ms	63788 KB	Output is correct
70	Correct	1359 ms	68640 KB	Output is correct
71	Correct	1351 ms	81192 KB	Output is correct
72	Correct	1340 ms	80088 KB	Output is correct
73	Correct	1134 ms	79784 KB	Output is correct
74	Correct	1114 ms	66440 KB	Output is correct
75	Correct	1115 ms	78708 KB	Output is correct
76	Correct	1168 ms	78472 KB	Output is correct
77	Correct	1120 ms	65528 KB	Output is correct
78	Correct	1194 ms	75060 KB	Output is correct
79	Correct	879 ms	58456 KB	Output is correct
80	Correct	1196 ms	71364 KB	Output is correct

답안 #172127

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