Submission #329757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
329757	2020-11-22T10:51:32 Z	Rainbowbunny	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2600 ms	262144 KB

sortbooks

#include <bits/stdc++.h>
using namespace std;

int n, q;
int w[1000005], L[1000005], blocking[1000005];
int ST[1000005][20], up[1000005][20], val[1000005][20];

stack <pair <int, int> > S;

int Query(int l, int r)
{
	if(l > r)
	{
		return 0;
	}
	int temp = L[r - l + 1];
	return max(ST[l][temp], ST[r - (1 << temp) + 1][temp]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	L[0] = -1;
	for(int i = 1; i <= n; i++)
	{
		L[i] = L[i >> 1] + 1;
		cin >> w[i];
		ST[i][0] = w[i];
	}
	for(int i = 1; i < 20; i++)
	{
		for(int j = 1; j + (1 << i) <= n + 1; j++)
		{
			ST[j][i] = max(ST[j][i - 1], ST[j + (1 << (i - 1))][i - 1]);
		}
	}
	for(int i = n; i >= 1; i--)
	{
		while(S.empty() == false && S.top().first < w[i])
		{
			S.pop();
		}
		if(S.empty())
		{
			up[i][0] = n + 1;
			if(Query(i + 1, n) == 0)
			{
				val[i][0] = 0;
			}
			else
			{
				val[i][0] = Query(i + 1, n) + w[i];
			}
		}
		else
		{
			up[i][0] = S.top().second;
			if(Query(i + 1, S.top().second - 1) == 0)
			{
				val[i][0] = 0;
			}
			else
			{
				val[i][0] = Query(i + 1, S.top().second - 1) + w[i];
			}
		}
		S.push(make_pair(w[i], i));
	}
	up[n + 1][0] = n + 1;
	val[n + 1][0] = 0;
	for(int i = 1; i < 20; i++)
	{
		up[n + 1][i] = n + 1;
		
		for(int j = n; j >= 1; j--)
		{
			up[j][i] = up[up[j][i - 1]][i - 1];
			val[j][i] = max(val[j][i - 1], val[up[j][i - 1]][i - 1]);
		}
	}
	while(q--)
	{
		int l, r, x;
		cin >> l >> r >> x;
		int tmp = 0;
		for(int i = 19; i >= 0; i--)
		{
			if(up[l][i] <= r)
			{
				tmp = max(tmp, val[l][i]);
				l = up[l][i];
			}
		}
		if(Query(l + 1, r) != 0)
		{
			tmp = max(tmp, Query(l + 1, r) + w[l]);
		}
		if(tmp > x)
		{
			cout << 0 << '\n';
		}
		else
		{
			cout << 1 << '\n';
		}
	}
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	508 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	508 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	3 ms	1516 KB	Output is correct
13	Correct	4 ms	1644 KB	Output is correct
14	Correct	5 ms	1772 KB	Output is correct
15	Correct	5 ms	1772 KB	Output is correct
16	Correct	5 ms	1772 KB	Output is correct
17	Correct	4 ms	1516 KB	Output is correct
18	Correct	4 ms	1772 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1633 ms	249928 KB	Output is correct
2	Correct	1680 ms	262144 KB	Output is correct
3	Correct	1649 ms	262144 KB	Output is correct
4	Correct	1651 ms	262144 KB	Output is correct
5	Correct	2568 ms	262144 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	24940 KB	Output is correct
2	Correct	117 ms	26964 KB	Output is correct
3	Correct	181 ms	27628 KB	Output is correct
4	Correct	186 ms	27884 KB	Output is correct
5	Correct	186 ms	27628 KB	Output is correct
6	Correct	114 ms	27372 KB	Output is correct
7	Correct	113 ms	27500 KB	Output is correct
8	Correct	144 ms	26988 KB	Output is correct
9	Correct	43 ms	2028 KB	Output is correct
10	Correct	139 ms	26988 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	508 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	3 ms	1516 KB	Output is correct
13	Correct	4 ms	1644 KB	Output is correct
14	Correct	5 ms	1772 KB	Output is correct
15	Correct	5 ms	1772 KB	Output is correct
16	Correct	5 ms	1772 KB	Output is correct
17	Correct	4 ms	1516 KB	Output is correct
18	Correct	4 ms	1772 KB	Output is correct
19	Correct	314 ms	56028 KB	Output is correct
20	Correct	303 ms	55916 KB	Output is correct
21	Correct	267 ms	55916 KB	Output is correct
22	Correct	268 ms	55788 KB	Output is correct
23	Correct	264 ms	55788 KB	Output is correct
24	Correct	351 ms	57324 KB	Output is correct
25	Correct	344 ms	57452 KB	Output is correct
26	Correct	403 ms	57580 KB	Output is correct
27	Correct	413 ms	57580 KB	Output is correct
28	Correct	440 ms	57580 KB	Output is correct
29	Correct	427 ms	57580 KB	Output is correct
30	Correct	431 ms	57708 KB	Output is correct
31	Correct	435 ms	57708 KB	Output is correct
32	Correct	436 ms	57580 KB	Output is correct
33	Correct	441 ms	57708 KB	Output is correct
34	Correct	262 ms	57196 KB	Output is correct
35	Correct	305 ms	57196 KB	Output is correct
36	Correct	250 ms	57012 KB	Output is correct
37	Correct	254 ms	56940 KB	Output is correct
38	Correct	265 ms	57196 KB	Output is correct
39	Correct	370 ms	55660 KB	Output is correct
40	Correct	279 ms	38080 KB	Output is correct
41	Correct	320 ms	54692 KB	Output is correct

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	508 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	3 ms	1516 KB	Output is correct
13	Correct	4 ms	1644 KB	Output is correct
14	Correct	5 ms	1772 KB	Output is correct
15	Correct	5 ms	1772 KB	Output is correct
16	Correct	5 ms	1772 KB	Output is correct
17	Correct	4 ms	1516 KB	Output is correct
18	Correct	4 ms	1772 KB	Output is correct
19	Correct	1633 ms	249928 KB	Output is correct
20	Correct	1680 ms	262144 KB	Output is correct
21	Correct	1649 ms	262144 KB	Output is correct
22	Correct	1651 ms	262144 KB	Output is correct
23	Correct	2568 ms	262144 KB	Output is correct
24	Correct	161 ms	24940 KB	Output is correct
25	Correct	117 ms	26964 KB	Output is correct
26	Correct	181 ms	27628 KB	Output is correct
27	Correct	186 ms	27884 KB	Output is correct
28	Correct	186 ms	27628 KB	Output is correct
29	Correct	114 ms	27372 KB	Output is correct
30	Correct	113 ms	27500 KB	Output is correct
31	Correct	144 ms	26988 KB	Output is correct
32	Correct	43 ms	2028 KB	Output is correct
33	Correct	139 ms	26988 KB	Output is correct
34	Correct	314 ms	56028 KB	Output is correct
35	Correct	303 ms	55916 KB	Output is correct
36	Correct	267 ms	55916 KB	Output is correct
37	Correct	268 ms	55788 KB	Output is correct
38	Correct	264 ms	55788 KB	Output is correct
39	Correct	351 ms	57324 KB	Output is correct
40	Correct	344 ms	57452 KB	Output is correct
41	Correct	403 ms	57580 KB	Output is correct
42	Correct	413 ms	57580 KB	Output is correct
43	Correct	440 ms	57580 KB	Output is correct
44	Correct	427 ms	57580 KB	Output is correct
45	Correct	431 ms	57708 KB	Output is correct
46	Correct	435 ms	57708 KB	Output is correct
47	Correct	436 ms	57580 KB	Output is correct
48	Correct	441 ms	57708 KB	Output is correct
49	Correct	262 ms	57196 KB	Output is correct
50	Correct	305 ms	57196 KB	Output is correct
51	Correct	250 ms	57012 KB	Output is correct
52	Correct	254 ms	56940 KB	Output is correct
53	Correct	265 ms	57196 KB	Output is correct
54	Correct	370 ms	55660 KB	Output is correct
55	Correct	279 ms	38080 KB	Output is correct
56	Correct	320 ms	54692 KB	Output is correct
57	Correct	1695 ms	262144 KB	Output is correct
58	Correct	1689 ms	262144 KB	Output is correct
59	Correct	1639 ms	262144 KB	Output is correct
60	Correct	1642 ms	262144 KB	Output is correct
61	Correct	1644 ms	262144 KB	Output is correct
62	Correct	1630 ms	262144 KB	Output is correct
63	Correct	1913 ms	262144 KB	Output is correct
64	Correct	1927 ms	262144 KB	Output is correct
65	Correct	2543 ms	262144 KB	Output is correct
66	Correct	2565 ms	262144 KB	Output is correct
67	Correct	2600 ms	262144 KB	Output is correct
68	Correct	2520 ms	262144 KB	Output is correct
69	Correct	2527 ms	262144 KB	Output is correct
70	Correct	2572 ms	262144 KB	Output is correct
71	Correct	2570 ms	262144 KB	Output is correct
72	Correct	2580 ms	262144 KB	Output is correct
73	Correct	1414 ms	262144 KB	Output is correct
74	Correct	1456 ms	262144 KB	Output is correct
75	Correct	1407 ms	262144 KB	Output is correct
76	Correct	1400 ms	262144 KB	Output is correct
77	Correct	1447 ms	262144 KB	Output is correct
78	Correct	2144 ms	262144 KB	Output is correct
79	Correct	1413 ms	155628 KB	Output is correct
80	Correct	1859 ms	262144 KB	Output is correct

Submission #329757

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