Submission #334404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334404	2020-12-09T06:05:50 Z	limabeans	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1867 ms	92284 KB

sortbooks

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl






const int inf = 2e9;
const int maxn = 1e6 + 5;


struct query {
    int l,r,k;
    void read() {
	cin>>l>>r>>k;
    }
};

int n,q;
int t[maxn*4];



void upd(int v, int tl, int tr, int i, int val) {
    if (tl==tr) {
	t[v]=max(t[v],val);
    } else {
	int tm=(tl+tr)/2;
	if (i<=tm) {
	    upd(2*v,tl,tm,i,val);
	} else {
	    upd(2*v+1,tm+1,tr,i,val);
	}
	t[v]=max(t[2*v],t[2*v+1]);
    }
}

int qry(int v, int tl, int tr, int l, int r) {
    if (l>tr || r<tl) return -inf;
    if (l<=tl && tr<=r) return t[v];
    int tm=(tl+tr)/2;
    return max(qry(2*v,tl,tm,l,r),qry(2*v+1,tm+1,tr,l,r));
}

int a[maxn];

query Q[maxn];
vector<int> ev[maxn];
int ans[maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>q;

    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
    for (int i=1; i<=q; i++) {
	Q[i].read();
	ev[Q[i].r].push_back(i);
    }

    stack<int> stk;
    vector<pair<int,int>> w;
    for (int i=1; i<=n; i++) {
	while (!stk.empty() && a[stk.top()]<=a[i]) stk.pop();
	if (!stk.empty()) w.push_back({i,stk.top()});
	stk.push(i);
    }

    sort(w.begin(),w.end());
    int j=0;
    for (int i=1; i<=n; i++) {
	while (j<(int)w.size() && w[j].first<=i) {
	    upd(1,1,n,w[j].second, a[w[j].first]+a[w[j].second]);
	    ++j;
	}

	for (int qi: ev[i]) {
	    if (qry(1,1,n,Q[qi].l,Q[qi].r)<=Q[qi].k) ans[qi]=1;
	}
    }
    


    for (int i=1; i<=q; i++) {
	cout<<ans[i]<<"\n";
    }
    
    
    return 0;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	18 ms	23788 KB	Output is correct
3	Correct	17 ms	23916 KB	Output is correct
4	Correct	16 ms	23916 KB	Output is correct
5	Correct	17 ms	23916 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23916 KB	Output is correct
8	Correct	17 ms	23916 KB	Output is correct
9	Correct	17 ms	23916 KB	Output is correct
10	Correct	17 ms	23916 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	18 ms	23788 KB	Output is correct
3	Correct	17 ms	23916 KB	Output is correct
4	Correct	16 ms	23916 KB	Output is correct
5	Correct	17 ms	23916 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23916 KB	Output is correct
8	Correct	17 ms	23916 KB	Output is correct
9	Correct	17 ms	23916 KB	Output is correct
10	Correct	17 ms	23916 KB	Output is correct
11	Correct	19 ms	24044 KB	Output is correct
12	Correct	20 ms	24172 KB	Output is correct
13	Correct	20 ms	24172 KB	Output is correct
14	Correct	22 ms	24300 KB	Output is correct
15	Correct	22 ms	24172 KB	Output is correct
16	Correct	23 ms	24172 KB	Output is correct
17	Correct	20 ms	24044 KB	Output is correct
18	Correct	20 ms	24172 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1860 ms	75732 KB	Output is correct
2	Correct	1865 ms	75848 KB	Output is correct
3	Correct	1849 ms	76584 KB	Output is correct
4	Correct	1855 ms	76744 KB	Output is correct
5	Correct	1524 ms	77420 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	29540 KB	Output is correct
2	Correct	132 ms	28896 KB	Output is correct
3	Correct	118 ms	27372 KB	Output is correct
4	Correct	117 ms	27628 KB	Output is correct
5	Correct	122 ms	27756 KB	Output is correct
6	Correct	98 ms	26476 KB	Output is correct
7	Correct	96 ms	26476 KB	Output is correct
8	Correct	111 ms	28512 KB	Output is correct
9	Correct	68 ms	26344 KB	Output is correct
10	Correct	109 ms	28388 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	18 ms	23788 KB	Output is correct
3	Correct	17 ms	23916 KB	Output is correct
4	Correct	16 ms	23916 KB	Output is correct
5	Correct	17 ms	23916 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23916 KB	Output is correct
8	Correct	17 ms	23916 KB	Output is correct
9	Correct	17 ms	23916 KB	Output is correct
10	Correct	17 ms	23916 KB	Output is correct
11	Correct	19 ms	24044 KB	Output is correct
12	Correct	20 ms	24172 KB	Output is correct
13	Correct	20 ms	24172 KB	Output is correct
14	Correct	22 ms	24300 KB	Output is correct
15	Correct	22 ms	24172 KB	Output is correct
16	Correct	23 ms	24172 KB	Output is correct
17	Correct	20 ms	24044 KB	Output is correct
18	Correct	20 ms	24172 KB	Output is correct
19	Correct	323 ms	35356 KB	Output is correct
20	Correct	330 ms	35164 KB	Output is correct
21	Correct	269 ms	33628 KB	Output is correct
22	Correct	268 ms	33628 KB	Output is correct
23	Correct	272 ms	33620 KB	Output is correct
24	Correct	220 ms	29804 KB	Output is correct
25	Correct	227 ms	29804 KB	Output is correct
26	Correct	248 ms	30444 KB	Output is correct
27	Correct	248 ms	30572 KB	Output is correct
28	Correct	258 ms	30720 KB	Output is correct
29	Correct	281 ms	31544 KB	Output is correct
30	Correct	277 ms	31596 KB	Output is correct
31	Correct	275 ms	31468 KB	Output is correct
32	Correct	273 ms	31468 KB	Output is correct
33	Correct	294 ms	31468 KB	Output is correct
34	Correct	206 ms	29548 KB	Output is correct
35	Correct	213 ms	29620 KB	Output is correct
36	Correct	206 ms	29548 KB	Output is correct
37	Correct	199 ms	29548 KB	Output is correct
38	Correct	204 ms	29548 KB	Output is correct
39	Correct	241 ms	32736 KB	Output is correct
40	Correct	188 ms	31332 KB	Output is correct
41	Correct	240 ms	32348 KB	Output is correct

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	18 ms	23788 KB	Output is correct
3	Correct	17 ms	23916 KB	Output is correct
4	Correct	16 ms	23916 KB	Output is correct
5	Correct	17 ms	23916 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	17 ms	23916 KB	Output is correct
8	Correct	17 ms	23916 KB	Output is correct
9	Correct	17 ms	23916 KB	Output is correct
10	Correct	17 ms	23916 KB	Output is correct
11	Correct	19 ms	24044 KB	Output is correct
12	Correct	20 ms	24172 KB	Output is correct
13	Correct	20 ms	24172 KB	Output is correct
14	Correct	22 ms	24300 KB	Output is correct
15	Correct	22 ms	24172 KB	Output is correct
16	Correct	23 ms	24172 KB	Output is correct
17	Correct	20 ms	24044 KB	Output is correct
18	Correct	20 ms	24172 KB	Output is correct
19	Correct	1860 ms	75732 KB	Output is correct
20	Correct	1865 ms	75848 KB	Output is correct
21	Correct	1849 ms	76584 KB	Output is correct
22	Correct	1855 ms	76744 KB	Output is correct
23	Correct	1524 ms	77420 KB	Output is correct
24	Correct	144 ms	29540 KB	Output is correct
25	Correct	132 ms	28896 KB	Output is correct
26	Correct	118 ms	27372 KB	Output is correct
27	Correct	117 ms	27628 KB	Output is correct
28	Correct	122 ms	27756 KB	Output is correct
29	Correct	98 ms	26476 KB	Output is correct
30	Correct	96 ms	26476 KB	Output is correct
31	Correct	111 ms	28512 KB	Output is correct
32	Correct	68 ms	26344 KB	Output is correct
33	Correct	109 ms	28388 KB	Output is correct
34	Correct	323 ms	35356 KB	Output is correct
35	Correct	330 ms	35164 KB	Output is correct
36	Correct	269 ms	33628 KB	Output is correct
37	Correct	268 ms	33628 KB	Output is correct
38	Correct	272 ms	33620 KB	Output is correct
39	Correct	220 ms	29804 KB	Output is correct
40	Correct	227 ms	29804 KB	Output is correct
41	Correct	248 ms	30444 KB	Output is correct
42	Correct	248 ms	30572 KB	Output is correct
43	Correct	258 ms	30720 KB	Output is correct
44	Correct	281 ms	31544 KB	Output is correct
45	Correct	277 ms	31596 KB	Output is correct
46	Correct	275 ms	31468 KB	Output is correct
47	Correct	273 ms	31468 KB	Output is correct
48	Correct	294 ms	31468 KB	Output is correct
49	Correct	206 ms	29548 KB	Output is correct
50	Correct	213 ms	29620 KB	Output is correct
51	Correct	206 ms	29548 KB	Output is correct
52	Correct	199 ms	29548 KB	Output is correct
53	Correct	204 ms	29548 KB	Output is correct
54	Correct	241 ms	32736 KB	Output is correct
55	Correct	188 ms	31332 KB	Output is correct
56	Correct	240 ms	32348 KB	Output is correct
57	Correct	1853 ms	92232 KB	Output is correct
58	Correct	1867 ms	92284 KB	Output is correct
59	Correct	1770 ms	88272 KB	Output is correct
60	Correct	1763 ms	88316 KB	Output is correct
61	Correct	1793 ms	88296 KB	Output is correct
62	Correct	1761 ms	88264 KB	Output is correct
63	Correct	1156 ms	65468 KB	Output is correct
64	Correct	1142 ms	66084 KB	Output is correct
65	Correct	1447 ms	71148 KB	Output is correct
66	Correct	1440 ms	71020 KB	Output is correct
67	Correct	1459 ms	71880 KB	Output is correct
68	Correct	1511 ms	76064 KB	Output is correct
69	Correct	1515 ms	76180 KB	Output is correct
70	Correct	1506 ms	75116 KB	Output is correct
71	Correct	1512 ms	71932 KB	Output is correct
72	Correct	1507 ms	75260 KB	Output is correct
73	Correct	1034 ms	64844 KB	Output is correct
74	Correct	1063 ms	64876 KB	Output is correct
75	Correct	1035 ms	64872 KB	Output is correct
76	Correct	1028 ms	64748 KB	Output is correct
77	Correct	1065 ms	64692 KB	Output is correct
78	Correct	1359 ms	74812 KB	Output is correct
79	Correct	980 ms	80328 KB	Output is correct
80	Correct	1362 ms	90952 KB	Output is correct

Submission #334404

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