Submission #503235

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503235	2022-01-07T14:45:07 Z	mosiashvililuka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	946 ms	94416 KB

sortbooks

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],K,tes,t,l,r,ans[1000009],F[1000009],fen[1000009];
pair <pair <int, int>, int> p[1000009];
vector <int> v[1000009];
stack <int> st;
void upd(int q, int w){
	q=a+2-q;
	while(q<=1000003){
		fen[q]=max(fen[q],w);
		q=q+(q&(-q));
	}
}
int read(int q){
	q=a+2-q;
	int sm=0;
	while(q>0){
		sm=max(sm,fen[q]);
		q=q-(q&(-q));
	}
	return sm;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	for(i=1; i<=a; i++) cin>>f[i];
	for(t=1; t<=tes; t++){
		cin>>p[t].first.first>>p[t].first.second>>p[t].second;
		v[p[t].first.second].push_back(t);
	}
	for(i=1; i<=a; i++){
		while(st.size()&&f[st.top()]<=f[i]) st.pop();
		if(st.size()){
			F[i]=st.top();
		}
		st.push(i);
	}
	for(i=1; i<=a; i++){
		if(F[i]!=0){
			upd(F[i],f[i]+f[F[i]]);
		}
		for(vector <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
			zx=read(p[(*it)].first.first);
			if(zx<=p[(*it)].second){
				ans[(*it)]=1;
			}else{
				ans[(*it)]=0;
			}
		}
	}
	for(t=1; t<=tes; t++){
		cout<<ans[t]<<"\n";
	}
	return 0;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23804 KB	Output is correct
2	Correct	12 ms	23816 KB	Output is correct
3	Correct	12 ms	23820 KB	Output is correct
4	Correct	12 ms	23884 KB	Output is correct
5	Correct	12 ms	23780 KB	Output is correct
6	Correct	13 ms	23868 KB	Output is correct
7	Correct	13 ms	23896 KB	Output is correct
8	Correct	12 ms	23888 KB	Output is correct
9	Correct	14 ms	23820 KB	Output is correct
10	Correct	13 ms	23816 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23804 KB	Output is correct
2	Correct	12 ms	23816 KB	Output is correct
3	Correct	12 ms	23820 KB	Output is correct
4	Correct	12 ms	23884 KB	Output is correct
5	Correct	12 ms	23780 KB	Output is correct
6	Correct	13 ms	23868 KB	Output is correct
7	Correct	13 ms	23896 KB	Output is correct
8	Correct	12 ms	23888 KB	Output is correct
9	Correct	14 ms	23820 KB	Output is correct
10	Correct	13 ms	23816 KB	Output is correct
11	Correct	12 ms	24012 KB	Output is correct
12	Correct	13 ms	24048 KB	Output is correct
13	Correct	13 ms	24056 KB	Output is correct
14	Correct	14 ms	24140 KB	Output is correct
15	Correct	16 ms	24140 KB	Output is correct
16	Correct	13 ms	24156 KB	Output is correct
17	Correct	14 ms	24120 KB	Output is correct
18	Correct	15 ms	24144 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	896 ms	71308 KB	Output is correct
2	Correct	896 ms	72844 KB	Output is correct
3	Correct	906 ms	73500 KB	Output is correct
4	Correct	908 ms	72680 KB	Output is correct
5	Correct	872 ms	73852 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	28632 KB	Output is correct
2	Correct	64 ms	29540 KB	Output is correct
3	Correct	59 ms	29252 KB	Output is correct
4	Correct	60 ms	29416 KB	Output is correct
5	Correct	64 ms	29568 KB	Output is correct
6	Correct	53 ms	28400 KB	Output is correct
7	Correct	52 ms	28408 KB	Output is correct
8	Correct	65 ms	29396 KB	Output is correct
9	Correct	42 ms	27424 KB	Output is correct
10	Correct	59 ms	29380 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23804 KB	Output is correct
2	Correct	12 ms	23816 KB	Output is correct
3	Correct	12 ms	23820 KB	Output is correct
4	Correct	12 ms	23884 KB	Output is correct
5	Correct	12 ms	23780 KB	Output is correct
6	Correct	13 ms	23868 KB	Output is correct
7	Correct	13 ms	23896 KB	Output is correct
8	Correct	12 ms	23888 KB	Output is correct
9	Correct	14 ms	23820 KB	Output is correct
10	Correct	13 ms	23816 KB	Output is correct
11	Correct	12 ms	24012 KB	Output is correct
12	Correct	13 ms	24048 KB	Output is correct
13	Correct	13 ms	24056 KB	Output is correct
14	Correct	14 ms	24140 KB	Output is correct
15	Correct	16 ms	24140 KB	Output is correct
16	Correct	13 ms	24156 KB	Output is correct
17	Correct	14 ms	24120 KB	Output is correct
18	Correct	15 ms	24144 KB	Output is correct
19	Correct	145 ms	36336 KB	Output is correct
20	Correct	148 ms	36356 KB	Output is correct
21	Correct	140 ms	34628 KB	Output is correct
22	Correct	128 ms	34720 KB	Output is correct
23	Correct	136 ms	34648 KB	Output is correct
24	Correct	119 ms	33028 KB	Output is correct
25	Correct	118 ms	32896 KB	Output is correct
26	Correct	123 ms	33532 KB	Output is correct
27	Correct	125 ms	33544 KB	Output is correct
28	Correct	128 ms	33704 KB	Output is correct
29	Correct	145 ms	34500 KB	Output is correct
30	Correct	143 ms	34460 KB	Output is correct
31	Correct	135 ms	34244 KB	Output is correct
32	Correct	147 ms	34240 KB	Output is correct
33	Correct	146 ms	34156 KB	Output is correct
34	Correct	109 ms	32096 KB	Output is correct
35	Correct	112 ms	31988 KB	Output is correct
36	Correct	103 ms	31844 KB	Output is correct
37	Correct	112 ms	31988 KB	Output is correct
38	Correct	109 ms	31812 KB	Output is correct
39	Correct	137 ms	34124 KB	Output is correct
40	Correct	110 ms	33132 KB	Output is correct
41	Correct	128 ms	33976 KB	Output is correct

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23804 KB	Output is correct
2	Correct	12 ms	23816 KB	Output is correct
3	Correct	12 ms	23820 KB	Output is correct
4	Correct	12 ms	23884 KB	Output is correct
5	Correct	12 ms	23780 KB	Output is correct
6	Correct	13 ms	23868 KB	Output is correct
7	Correct	13 ms	23896 KB	Output is correct
8	Correct	12 ms	23888 KB	Output is correct
9	Correct	14 ms	23820 KB	Output is correct
10	Correct	13 ms	23816 KB	Output is correct
11	Correct	12 ms	24012 KB	Output is correct
12	Correct	13 ms	24048 KB	Output is correct
13	Correct	13 ms	24056 KB	Output is correct
14	Correct	14 ms	24140 KB	Output is correct
15	Correct	16 ms	24140 KB	Output is correct
16	Correct	13 ms	24156 KB	Output is correct
17	Correct	14 ms	24120 KB	Output is correct
18	Correct	15 ms	24144 KB	Output is correct
19	Correct	896 ms	71308 KB	Output is correct
20	Correct	896 ms	72844 KB	Output is correct
21	Correct	906 ms	73500 KB	Output is correct
22	Correct	908 ms	72680 KB	Output is correct
23	Correct	872 ms	73852 KB	Output is correct
24	Correct	66 ms	28632 KB	Output is correct
25	Correct	64 ms	29540 KB	Output is correct
26	Correct	59 ms	29252 KB	Output is correct
27	Correct	60 ms	29416 KB	Output is correct
28	Correct	64 ms	29568 KB	Output is correct
29	Correct	53 ms	28400 KB	Output is correct
30	Correct	52 ms	28408 KB	Output is correct
31	Correct	65 ms	29396 KB	Output is correct
32	Correct	42 ms	27424 KB	Output is correct
33	Correct	59 ms	29380 KB	Output is correct
34	Correct	145 ms	36336 KB	Output is correct
35	Correct	148 ms	36356 KB	Output is correct
36	Correct	140 ms	34628 KB	Output is correct
37	Correct	128 ms	34720 KB	Output is correct
38	Correct	136 ms	34648 KB	Output is correct
39	Correct	119 ms	33028 KB	Output is correct
40	Correct	118 ms	32896 KB	Output is correct
41	Correct	123 ms	33532 KB	Output is correct
42	Correct	125 ms	33544 KB	Output is correct
43	Correct	128 ms	33704 KB	Output is correct
44	Correct	145 ms	34500 KB	Output is correct
45	Correct	143 ms	34460 KB	Output is correct
46	Correct	135 ms	34244 KB	Output is correct
47	Correct	147 ms	34240 KB	Output is correct
48	Correct	146 ms	34156 KB	Output is correct
49	Correct	109 ms	32096 KB	Output is correct
50	Correct	112 ms	31988 KB	Output is correct
51	Correct	103 ms	31844 KB	Output is correct
52	Correct	112 ms	31988 KB	Output is correct
53	Correct	109 ms	31812 KB	Output is correct
54	Correct	137 ms	34124 KB	Output is correct
55	Correct	110 ms	33132 KB	Output is correct
56	Correct	128 ms	33976 KB	Output is correct
57	Correct	886 ms	79636 KB	Output is correct
58	Correct	891 ms	79768 KB	Output is correct
59	Correct	859 ms	75620 KB	Output is correct
60	Correct	942 ms	75612 KB	Output is correct
61	Correct	946 ms	75620 KB	Output is correct
62	Correct	849 ms	75620 KB	Output is correct
63	Correct	584 ms	61436 KB	Output is correct
64	Correct	588 ms	61436 KB	Output is correct
65	Correct	780 ms	67276 KB	Output is correct
66	Correct	790 ms	87236 KB	Output is correct
67	Correct	805 ms	61096 KB	Output is correct
68	Correct	878 ms	77364 KB	Output is correct
69	Correct	895 ms	94416 KB	Output is correct
70	Correct	889 ms	75748 KB	Output is correct
71	Correct	832 ms	76292 KB	Output is correct
72	Correct	858 ms	92604 KB	Output is correct
73	Correct	547 ms	63376 KB	Output is correct
74	Correct	577 ms	79136 KB	Output is correct
75	Correct	540 ms	78964 KB	Output is correct
76	Correct	545 ms	81416 KB	Output is correct
77	Correct	542 ms	81148 KB	Output is correct
78	Correct	725 ms	85992 KB	Output is correct
79	Correct	563 ms	60976 KB	Output is correct
80	Correct	733 ms	86776 KB	Output is correct

Submission #503235

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