oj.uz

Submission #898364

# Submission time Handle Problem Language Result Execution time Memory
898364 2024-01-04T14:23:22 Z penguin133 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1437 ms 217428 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n,m,q;
stack<int>st;
struct node{
	int s,e,m,val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	void upd(int p, int v){
		if(s == e)val = max(val, v);
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
			val = max(l->val, r->val);
		}
	}
	int query(int a, int b){
		if(s == a && e == b)return val;
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return max(l->query(a, m), r->query(m+1, b));
	}
}*root;
int A[1000005], ans[1000005];
vector<pii> Q[1000005];
void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	for(int i=1;i<=q;i++){
		int x,y,z;
		cin >> x >> y >> z;
		Q[y].push_back({x, {z, i}});
	}
	root = new node(1, n);
	for(int i=1;i<=n;i++){
		while(!st.empty() && A[st.top()] <= A[i])st.pop();
		if(!st.empty()){
			int x = st.top();
			root->upd(x, A[st.top()] + A[i]);		
		}
		for(auto j : Q[i]){
			int x = j.fi, y = j.se.fi, z = j.se.se;
			ans[z] = (root->query(x, i) <= y);
		}
		st.push(i);
	}
	for(int i=1;i<=q;i++)cout << ans[i] << "\n";
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

sortbooks.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 6 ms 29268 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 6 ms 29336 KB Output is correct
6 Correct 6 ms 29344 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29260 KB Output is correct
9 Correct 6 ms 29272 KB Output is correct
10 Correct 6 ms 29272 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 6 ms 29268 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 6 ms 29336 KB Output is correct
6 Correct 6 ms 29344 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29260 KB Output is correct
9 Correct 6 ms 29272 KB Output is correct
10 Correct 6 ms 29272 KB Output is correct
11 Correct 7 ms 29528 KB Output is correct
12 Correct 8 ms 30132 KB Output is correct
13 Correct 8 ms 30112 KB Output is correct
14 Correct 10 ms 30044 KB Output is correct
15 Correct 10 ms 30044 KB Output is correct
16 Correct 8 ms 30064 KB Output is correct
17 Correct 8 ms 30044 KB Output is correct
18 Correct 8 ms 30296 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 211892 KB Output is correct
2 Correct 1408 ms 216516 KB Output is correct
3 Correct 1425 ms 216244 KB Output is correct
4 Correct 1411 ms 216588 KB Output is correct
5 Correct 1326 ms 216660 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 46540 KB Output is correct
2 Correct 75 ms 46628 KB Output is correct
3 Correct 73 ms 46432 KB Output is correct
4 Correct 77 ms 46464 KB Output is correct
5 Correct 74 ms 46380 KB Output is correct
6 Correct 57 ms 46184 KB Output is correct
7 Correct 58 ms 46160 KB Output is correct
8 Correct 69 ms 45900 KB Output is correct
9 Correct 31 ms 33284 KB Output is correct
10 Correct 65 ms 46020 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 6 ms 29268 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 6 ms 29336 KB Output is correct
6 Correct 6 ms 29344 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29260 KB Output is correct
9 Correct 6 ms 29272 KB Output is correct
10 Correct 6 ms 29272 KB Output is correct
11 Correct 7 ms 29528 KB Output is correct
12 Correct 8 ms 30132 KB Output is correct
13 Correct 8 ms 30112 KB Output is correct
14 Correct 10 ms 30044 KB Output is correct
15 Correct 10 ms 30044 KB Output is correct
16 Correct 8 ms 30064 KB Output is correct
17 Correct 8 ms 30044 KB Output is correct
18 Correct 8 ms 30296 KB Output is correct
19 Correct 205 ms 66976 KB Output is correct
20 Correct 206 ms 67144 KB Output is correct
21 Correct 155 ms 67100 KB Output is correct
22 Correct 158 ms 67124 KB Output is correct
23 Correct 162 ms 67164 KB Output is correct
24 Correct 128 ms 66896 KB Output is correct
25 Correct 127 ms 66896 KB Output is correct
26 Correct 156 ms 67156 KB Output is correct
27 Correct 149 ms 67152 KB Output is correct
28 Correct 154 ms 67156 KB Output is correct
29 Correct 189 ms 67152 KB Output is correct
30 Correct 177 ms 66980 KB Output is correct
31 Correct 174 ms 66900 KB Output is correct
32 Correct 187 ms 66984 KB Output is correct
33 Correct 172 ms 66896 KB Output is correct
34 Correct 116 ms 66128 KB Output is correct
35 Correct 116 ms 66124 KB Output is correct
36 Correct 117 ms 66132 KB Output is correct
37 Correct 115 ms 66236 KB Output is correct
38 Correct 116 ms 66132 KB Output is correct
39 Correct 153 ms 65540 KB Output is correct
40 Correct 120 ms 55928 KB Output is correct
41 Correct 149 ms 65972 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 6 ms 29268 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 6 ms 29336 KB Output is correct
6 Correct 6 ms 29344 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29260 KB Output is correct
9 Correct 6 ms 29272 KB Output is correct
10 Correct 6 ms 29272 KB Output is correct
11 Correct 7 ms 29528 KB Output is correct
12 Correct 8 ms 30132 KB Output is correct
13 Correct 8 ms 30112 KB Output is correct
14 Correct 10 ms 30044 KB Output is correct
15 Correct 10 ms 30044 KB Output is correct
16 Correct 8 ms 30064 KB Output is correct
17 Correct 8 ms 30044 KB Output is correct
18 Correct 8 ms 30296 KB Output is correct
19 Correct 1437 ms 211892 KB Output is correct
20 Correct 1408 ms 216516 KB Output is correct
21 Correct 1425 ms 216244 KB Output is correct
22 Correct 1411 ms 216588 KB Output is correct
23 Correct 1326 ms 216660 KB Output is correct
24 Correct 90 ms 46540 KB Output is correct
25 Correct 75 ms 46628 KB Output is correct
26 Correct 73 ms 46432 KB Output is correct
27 Correct 77 ms 46464 KB Output is correct
28 Correct 74 ms 46380 KB Output is correct
29 Correct 57 ms 46184 KB Output is correct
30 Correct 58 ms 46160 KB Output is correct
31 Correct 69 ms 45900 KB Output is correct
32 Correct 31 ms 33284 KB Output is correct
33 Correct 65 ms 46020 KB Output is correct
34 Correct 205 ms 66976 KB Output is correct
35 Correct 206 ms 67144 KB Output is correct
36 Correct 155 ms 67100 KB Output is correct
37 Correct 158 ms 67124 KB Output is correct
38 Correct 162 ms 67164 KB Output is correct
39 Correct 128 ms 66896 KB Output is correct
40 Correct 127 ms 66896 KB Output is correct
41 Correct 156 ms 67156 KB Output is correct
42 Correct 149 ms 67152 KB Output is correct
43 Correct 154 ms 67156 KB Output is correct
44 Correct 189 ms 67152 KB Output is correct
45 Correct 177 ms 66980 KB Output is correct
46 Correct 174 ms 66900 KB Output is correct
47 Correct 187 ms 66984 KB Output is correct
48 Correct 172 ms 66896 KB Output is correct
49 Correct 116 ms 66128 KB Output is correct
50 Correct 116 ms 66124 KB Output is correct
51 Correct 117 ms 66132 KB Output is correct
52 Correct 115 ms 66236 KB Output is correct
53 Correct 116 ms 66132 KB Output is correct
54 Correct 153 ms 65540 KB Output is correct
55 Correct 120 ms 55928 KB Output is correct
56 Correct 149 ms 65972 KB Output is correct
57 Correct 1376 ms 216596 KB Output is correct
58 Correct 1356 ms 216416 KB Output is correct
59 Correct 1176 ms 217216 KB Output is correct
60 Correct 1210 ms 217172 KB Output is correct
61 Correct 1196 ms 217004 KB Output is correct
62 Correct 1185 ms 216980 KB Output is correct
63 Correct 614 ms 215780 KB Output is correct
64 Correct 618 ms 215840 KB Output is correct
65 Correct 1032 ms 217428 KB Output is correct
66 Correct 1052 ms 217112 KB Output is correct
67 Correct 1063 ms 217168 KB Output is correct
68 Correct 1209 ms 216508 KB Output is correct
69 Correct 1208 ms 216228 KB Output is correct
70 Correct 1184 ms 216404 KB Output is correct
71 Correct 1206 ms 216028 KB Output is correct
72 Correct 1241 ms 216780 KB Output is correct
73 Correct 600 ms 208560 KB Output is correct
74 Correct 573 ms 208928 KB Output is correct
75 Correct 563 ms 208380 KB Output is correct
76 Correct 582 ms 208724 KB Output is correct
77 Correct 558 ms 193120 KB Output is correct
78 Correct 1010 ms 197116 KB Output is correct
79 Correct 730 ms 135052 KB Output is correct
80 Correct 996 ms 196500 KB Output is correct