oj.uz

Submission #898362

# Submission time Handle Problem Language Result Execution time Memory
898362 2024-01-04T14:21:49 Z penguin133 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1524 ms 234068 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, q, A[1000005];

struct node{
	int s, e, m, val, lz;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		lz = val = 0;
	}
	
	void prop(){
		if(lz){
			val = lz;
			if(s != e)l->lz = lz, r->lz = lz;
			lz = 0;
		}
	}
	
	void upd(int a, int b, int c){
		prop();
		if(a == s && b == e)lz = c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->prop(), r->prop();
			val = max(l->val, r->val);
		}
	}
	
	int qry(int x){
		prop();
		if(s == e)return (val >= x ? s : 0);
		r->prop();
		if(r->val >= x)return r->qry(x);
		else return l->qry(x);
	}
	
	int qval(int x){
		prop();
		if(s == e)return val;
		if(x <= m)return l->qval(x);
		return r->qval(x);
	}
}*root;
int ans[1000005];
vector <pii> Q[1000005];

void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	root = new node(1, n);
	stack <int> s;
	for(int i=1;i<=q;i++){
		int l, r, k;
		cin >> l >> r >> k;
		Q[r].push_back({l, {k, i}});
	}
	for(int i=1;i<=n;i++){
		while(!s.empty() && A[s.top()] <= A[i])s.pop();
		if(!s.empty()){
			int x = s.top();
			int tmp = root->qry(A[x] + A[i]);
			
			if(tmp + 1 <= x)root->upd(tmp + 1, x, A[x] + A[i]);
		}
		s.push(i);
		for(auto j : Q[i]){
			ans[j.se.se] = (root->qval(j.fi) <= j.se.fi);
		}
	}
	for(int i=1;i<=q;i++)cout << ans[i] << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29272 KB Output is correct
2 Correct 7 ms 29536 KB Output is correct
3 Correct 6 ms 29312 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 6 ms 29272 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 6 ms 29276 KB Output is correct
11 Correct 8 ms 29532 KB Output is correct
12 Correct 9 ms 30040 KB Output is correct
13 Correct 9 ms 30044 KB Output is correct
14 Correct 12 ms 30112 KB Output is correct
15 Correct 10 ms 30044 KB Output is correct
16 Correct 9 ms 30056 KB Output is correct
17 Correct 8 ms 30040 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1502 ms 199304 KB Output is correct
2 Correct 1494 ms 199676 KB Output is correct
3 Correct 1499 ms 199084 KB Output is correct
4 Correct 1507 ms 199252 KB Output is correct
5 Correct 1162 ms 199168 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 45140 KB Output is correct
2 Correct 76 ms 47260 KB Output is correct
3 Correct 65 ms 47132 KB Output is correct
4 Correct 70 ms 47188 KB Output is correct
5 Correct 72 ms 47268 KB Output is correct
6 Correct 46 ms 47184 KB Output is correct
7 Correct 47 ms 47184 KB Output is correct
8 Correct 63 ms 46932 KB Output is correct
9 Correct 32 ms 33792 KB Output is correct
10 Correct 66 ms 46932 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29272 KB Output is correct
2 Correct 7 ms 29536 KB Output is correct
3 Correct 6 ms 29312 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 6 ms 29272 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 6 ms 29276 KB Output is correct
11 Correct 8 ms 29532 KB Output is correct
12 Correct 9 ms 30040 KB Output is correct
13 Correct 9 ms 30044 KB Output is correct
14 Correct 12 ms 30112 KB Output is correct
15 Correct 10 ms 30044 KB Output is correct
16 Correct 9 ms 30056 KB Output is correct
17 Correct 8 ms 30040 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct
19 Correct 217 ms 69456 KB Output is correct
20 Correct 224 ms 69340 KB Output is correct
21 Correct 159 ms 70092 KB Output is correct
22 Correct 161 ms 69968 KB Output is correct
23 Correct 163 ms 69984 KB Output is correct
24 Correct 114 ms 69788 KB Output is correct
25 Correct 110 ms 69712 KB Output is correct
26 Correct 140 ms 69920 KB Output is correct
27 Correct 146 ms 69752 KB Output is correct
28 Correct 140 ms 69440 KB Output is correct
29 Correct 163 ms 69456 KB Output is correct
30 Correct 177 ms 69492 KB Output is correct
31 Correct 165 ms 69456 KB Output is correct
32 Correct 171 ms 69516 KB Output is correct
33 Correct 171 ms 69348 KB Output is correct
34 Correct 100 ms 69200 KB Output is correct
35 Correct 103 ms 69228 KB Output is correct
36 Correct 100 ms 68944 KB Output is correct
37 Correct 100 ms 69056 KB Output is correct
38 Correct 102 ms 69112 KB Output is correct
39 Correct 188 ms 67844 KB Output is correct
40 Correct 116 ms 57848 KB Output is correct
41 Correct 143 ms 67204 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29272 KB Output is correct
2 Correct 7 ms 29536 KB Output is correct
3 Correct 6 ms 29312 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 6 ms 29272 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 6 ms 29276 KB Output is correct
11 Correct 8 ms 29532 KB Output is correct
12 Correct 9 ms 30040 KB Output is correct
13 Correct 9 ms 30044 KB Output is correct
14 Correct 12 ms 30112 KB Output is correct
15 Correct 10 ms 30044 KB Output is correct
16 Correct 9 ms 30056 KB Output is correct
17 Correct 8 ms 30040 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct
19 Correct 1502 ms 199304 KB Output is correct
20 Correct 1494 ms 199676 KB Output is correct
21 Correct 1499 ms 199084 KB Output is correct
22 Correct 1507 ms 199252 KB Output is correct
23 Correct 1162 ms 199168 KB Output is correct
24 Correct 106 ms 45140 KB Output is correct
25 Correct 76 ms 47260 KB Output is correct
26 Correct 65 ms 47132 KB Output is correct
27 Correct 70 ms 47188 KB Output is correct
28 Correct 72 ms 47268 KB Output is correct
29 Correct 46 ms 47184 KB Output is correct
30 Correct 47 ms 47184 KB Output is correct
31 Correct 63 ms 46932 KB Output is correct
32 Correct 32 ms 33792 KB Output is correct
33 Correct 66 ms 46932 KB Output is correct
34 Correct 217 ms 69456 KB Output is correct
35 Correct 224 ms 69340 KB Output is correct
36 Correct 159 ms 70092 KB Output is correct
37 Correct 161 ms 69968 KB Output is correct
38 Correct 163 ms 69984 KB Output is correct
39 Correct 114 ms 69788 KB Output is correct
40 Correct 110 ms 69712 KB Output is correct
41 Correct 140 ms 69920 KB Output is correct
42 Correct 146 ms 69752 KB Output is correct
43 Correct 140 ms 69440 KB Output is correct
44 Correct 163 ms 69456 KB Output is correct
45 Correct 177 ms 69492 KB Output is correct
46 Correct 165 ms 69456 KB Output is correct
47 Correct 171 ms 69516 KB Output is correct
48 Correct 171 ms 69348 KB Output is correct
49 Correct 100 ms 69200 KB Output is correct
50 Correct 103 ms 69228 KB Output is correct
51 Correct 100 ms 68944 KB Output is correct
52 Correct 100 ms 69056 KB Output is correct
53 Correct 102 ms 69112 KB Output is correct
54 Correct 188 ms 67844 KB Output is correct
55 Correct 116 ms 57848 KB Output is correct
56 Correct 143 ms 67204 KB Output is correct
57 Correct 1524 ms 228968 KB Output is correct
58 Correct 1476 ms 233128 KB Output is correct
59 Correct 1302 ms 233608 KB Output is correct
60 Correct 1285 ms 234004 KB Output is correct
61 Correct 1301 ms 233588 KB Output is correct
62 Correct 1266 ms 233716 KB Output is correct
63 Correct 517 ms 233968 KB Output is correct
64 Correct 519 ms 233808 KB Output is correct
65 Correct 947 ms 233856 KB Output is correct
66 Correct 941 ms 234068 KB Output is correct
67 Correct 1046 ms 233944 KB Output is correct
68 Correct 1121 ms 233112 KB Output is correct
69 Correct 1126 ms 232956 KB Output is correct
70 Correct 1132 ms 233160 KB Output is correct
71 Correct 1091 ms 232916 KB Output is correct
72 Correct 1077 ms 232900 KB Output is correct
73 Correct 472 ms 227532 KB Output is correct
74 Correct 475 ms 228736 KB Output is correct
75 Correct 461 ms 227924 KB Output is correct
76 Correct 468 ms 227916 KB Output is correct
77 Correct 480 ms 227568 KB Output is correct
78 Correct 1048 ms 224460 KB Output is correct
79 Correct 704 ms 157576 KB Output is correct
80 Correct 950 ms 222048 KB Output is correct