Submission #774237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774237	2023-07-05T13:20:09 Z	NintsiChkhaidze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2329 ms	133616 KB

sortbooks

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pll pair <ll,ll>
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 1e6 + 5,inf = 1e9;

int a[N],le[N],ri[N],ans[N],k[N];
int t[4*N];
vector <int> v[N];

void upd(int h,int l,int r,int idx,int val){
	if (l == r){
		t[h] = max(t[h],val);
		return;
	}

	int mid = (l + r)/2;
	if (idx > mid) upd(right,idx,val);
	else upd(left,idx,val);
	t[h] = max(t[h*2],t[h*2 + 1]);
}

int get(int h,int l,int r,int L,int R){
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return t[h];
	return max(get(left,L,R),get(right,L,R));
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,Q;
	cin>>n>>Q;

	for (int i = 1; i <= n; i++){
		cin>>a[i];
	}

	for (int i = 1; i <= Q; i++){
		cin>>le[i]>>ri[i]>>k[i];
		v[ri[i]].pb(i);
	}

	deque <int> dq;
	for (int i = 1; i <= n; i++){
		while (dq.size() && a[dq.back()] <= a[i]){
			dq.pop_back();
		}
		if (dq.size()){
			upd(1,1,n,dq.back(),a[i] + a[dq.back()]);
		}
		dq.pb(i);

		for (int id: v[i]){
			if (get(1,1,n,le[id],i) <= k[id]) ans[id] = 1;
		}
	}

	for (int i = 1; i <= Q; i++)
		cout<<ans[i]<<endl;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	12 ms	23768 KB	Output is correct
3	Correct	11 ms	23764 KB	Output is correct
4	Correct	11 ms	23768 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23892 KB	Output is correct
7	Correct	12 ms	23860 KB	Output is correct
8	Correct	12 ms	23892 KB	Output is correct
9	Correct	12 ms	23832 KB	Output is correct
10	Correct	12 ms	23776 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	12 ms	23768 KB	Output is correct
3	Correct	11 ms	23764 KB	Output is correct
4	Correct	11 ms	23768 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23892 KB	Output is correct
7	Correct	12 ms	23860 KB	Output is correct
8	Correct	12 ms	23892 KB	Output is correct
9	Correct	12 ms	23832 KB	Output is correct
10	Correct	12 ms	23776 KB	Output is correct
11	Correct	15 ms	24020 KB	Output is correct
12	Correct	15 ms	24148 KB	Output is correct
13	Correct	16 ms	24212 KB	Output is correct
14	Correct	19 ms	24356 KB	Output is correct
15	Correct	25 ms	24432 KB	Output is correct
16	Correct	18 ms	24276 KB	Output is correct
17	Correct	18 ms	24228 KB	Output is correct
18	Correct	20 ms	24240 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2161 ms	93340 KB	Output is correct
2	Correct	2161 ms	93348 KB	Output is correct
3	Correct	2150 ms	93316 KB	Output is correct
4	Correct	2143 ms	93332 KB	Output is correct
5	Correct	1946 ms	84768 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	181 ms	31820 KB	Output is correct
2	Correct	173 ms	33336 KB	Output is correct
3	Correct	165 ms	31628 KB	Output is correct
4	Correct	174 ms	31672 KB	Output is correct
5	Correct	167 ms	31780 KB	Output is correct
6	Correct	152 ms	30156 KB	Output is correct
7	Correct	152 ms	30156 KB	Output is correct
8	Correct	158 ms	31328 KB	Output is correct
9	Correct	132 ms	29380 KB	Output is correct
10	Correct	160 ms	31404 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	12 ms	23768 KB	Output is correct
3	Correct	11 ms	23764 KB	Output is correct
4	Correct	11 ms	23768 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23892 KB	Output is correct
7	Correct	12 ms	23860 KB	Output is correct
8	Correct	12 ms	23892 KB	Output is correct
9	Correct	12 ms	23832 KB	Output is correct
10	Correct	12 ms	23776 KB	Output is correct
11	Correct	15 ms	24020 KB	Output is correct
12	Correct	15 ms	24148 KB	Output is correct
13	Correct	16 ms	24212 KB	Output is correct
14	Correct	19 ms	24356 KB	Output is correct
15	Correct	25 ms	24432 KB	Output is correct
16	Correct	18 ms	24276 KB	Output is correct
17	Correct	18 ms	24228 KB	Output is correct
18	Correct	20 ms	24240 KB	Output is correct
19	Correct	383 ms	46600 KB	Output is correct
20	Correct	366 ms	46512 KB	Output is correct
21	Correct	353 ms	45376 KB	Output is correct
22	Correct	349 ms	45228 KB	Output is correct
23	Correct	356 ms	45120 KB	Output is correct
24	Correct	317 ms	40880 KB	Output is correct
25	Correct	327 ms	40932 KB	Output is correct
26	Correct	331 ms	41488 KB	Output is correct
27	Correct	346 ms	41580 KB	Output is correct
28	Correct	336 ms	41672 KB	Output is correct
29	Correct	346 ms	42428 KB	Output is correct
30	Correct	345 ms	42316 KB	Output is correct
31	Correct	367 ms	42268 KB	Output is correct
32	Correct	342 ms	42336 KB	Output is correct
33	Correct	348 ms	42392 KB	Output is correct
34	Correct	313 ms	40548 KB	Output is correct
35	Correct	308 ms	40564 KB	Output is correct
36	Correct	307 ms	40420 KB	Output is correct
37	Correct	306 ms	40308 KB	Output is correct
38	Correct	306 ms	40608 KB	Output is correct
39	Correct	332 ms	42036 KB	Output is correct
40	Correct	316 ms	39028 KB	Output is correct
41	Correct	321 ms	40320 KB	Output is correct

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	12 ms	23768 KB	Output is correct
3	Correct	11 ms	23764 KB	Output is correct
4	Correct	11 ms	23768 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23892 KB	Output is correct
7	Correct	12 ms	23860 KB	Output is correct
8	Correct	12 ms	23892 KB	Output is correct
9	Correct	12 ms	23832 KB	Output is correct
10	Correct	12 ms	23776 KB	Output is correct
11	Correct	15 ms	24020 KB	Output is correct
12	Correct	15 ms	24148 KB	Output is correct
13	Correct	16 ms	24212 KB	Output is correct
14	Correct	19 ms	24356 KB	Output is correct
15	Correct	25 ms	24432 KB	Output is correct
16	Correct	18 ms	24276 KB	Output is correct
17	Correct	18 ms	24228 KB	Output is correct
18	Correct	20 ms	24240 KB	Output is correct
19	Correct	2161 ms	93340 KB	Output is correct
20	Correct	2161 ms	93348 KB	Output is correct
21	Correct	2150 ms	93316 KB	Output is correct
22	Correct	2143 ms	93332 KB	Output is correct
23	Correct	1946 ms	84768 KB	Output is correct
24	Correct	181 ms	31820 KB	Output is correct
25	Correct	173 ms	33336 KB	Output is correct
26	Correct	165 ms	31628 KB	Output is correct
27	Correct	174 ms	31672 KB	Output is correct
28	Correct	167 ms	31780 KB	Output is correct
29	Correct	152 ms	30156 KB	Output is correct
30	Correct	152 ms	30156 KB	Output is correct
31	Correct	158 ms	31328 KB	Output is correct
32	Correct	132 ms	29380 KB	Output is correct
33	Correct	160 ms	31404 KB	Output is correct
34	Correct	383 ms	46600 KB	Output is correct
35	Correct	366 ms	46512 KB	Output is correct
36	Correct	353 ms	45376 KB	Output is correct
37	Correct	349 ms	45228 KB	Output is correct
38	Correct	356 ms	45120 KB	Output is correct
39	Correct	317 ms	40880 KB	Output is correct
40	Correct	327 ms	40932 KB	Output is correct
41	Correct	331 ms	41488 KB	Output is correct
42	Correct	346 ms	41580 KB	Output is correct
43	Correct	336 ms	41672 KB	Output is correct
44	Correct	346 ms	42428 KB	Output is correct
45	Correct	345 ms	42316 KB	Output is correct
46	Correct	367 ms	42268 KB	Output is correct
47	Correct	342 ms	42336 KB	Output is correct
48	Correct	348 ms	42392 KB	Output is correct
49	Correct	313 ms	40548 KB	Output is correct
50	Correct	308 ms	40564 KB	Output is correct
51	Correct	307 ms	40420 KB	Output is correct
52	Correct	306 ms	40308 KB	Output is correct
53	Correct	306 ms	40608 KB	Output is correct
54	Correct	332 ms	42036 KB	Output is correct
55	Correct	316 ms	39028 KB	Output is correct
56	Correct	321 ms	40320 KB	Output is correct
57	Correct	2227 ms	133604 KB	Output is correct
58	Correct	2208 ms	133616 KB	Output is correct
59	Correct	2315 ms	130800 KB	Output is correct
60	Correct	2283 ms	130788 KB	Output is correct
61	Correct	2170 ms	130828 KB	Output is correct
62	Correct	2323 ms	130844 KB	Output is correct
63	Correct	1698 ms	108996 KB	Output is correct
64	Correct	1736 ms	109024 KB	Output is correct
65	Correct	2097 ms	114188 KB	Output is correct
66	Correct	1921 ms	114452 KB	Output is correct
67	Correct	1899 ms	114308 KB	Output is correct
68	Correct	1940 ms	117164 KB	Output is correct
69	Correct	2041 ms	117192 KB	Output is correct
70	Correct	2237 ms	116752 KB	Output is correct
71	Correct	2078 ms	116696 KB	Output is correct
72	Correct	2329 ms	116768 KB	Output is correct
73	Correct	2102 ms	106004 KB	Output is correct
74	Correct	1928 ms	106736 KB	Output is correct
75	Correct	1893 ms	105872 KB	Output is correct
76	Correct	1981 ms	105956 KB	Output is correct
77	Correct	1824 ms	105724 KB	Output is correct
78	Correct	2139 ms	114800 KB	Output is correct
79	Correct	1989 ms	98508 KB	Output is correct
80	Correct	2215 ms	106876 KB	Output is correct

Submission #774237

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