oj.uz

Submission #1092688

# Submission time Handle Problem Language Result Execution time Memory
1092688 2024-09-24T18:21:27 Z 4QT0R Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 726 ms 145684 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct query{
	ll x;
	ll y;
	ll k;
	ll ind;
	ll type;
};

ll wej[1000003];
vector<query> ev;

const ll base=1<<20;
ll tree[2*base];
void update(ll v, ll x){
	v+=base;
	if (tree[v]>=x)return;
	tree[v]=x;
	v>>=1;
	while(v){
		tree[v]=max(tree[2*v],tree[2*v+1]);
		v>>=1;
	}
}
ll check(ll p){
	ll ans=0;
	p+=base+1;
	while(p/2){
		if (p&1)ans=max(ans,tree[p-1]);
		p>>=1;
	}
	return ans;
}
ll odpow[1000003];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll n,m;
	cin >> n >> m;
	stack<pair<ll,ll>> st;
	for (ll i = 1; i<=n; i++){
		cin >> wej[i];
		while(st.size() && st.top().first<=wej[i])st.pop();
		if (st.size())ev.push_back({st.top().second,i,st.top().first+wej[i],i,0});
		st.push({wej[i],i});
	}
	for (ll i = 1,a,b,c; i<=m; i++){
		cin >> a >> b >> c;
		ev.push_back({a,b,c,i,1});
	}
	sort(ev.begin(),ev.end(),[](query a, query b){return a.x==b.x?a.type<b.type:a.x>b.x;});
	for (ll i = 0; i<ev.size(); i++){
		if (ev[i].type)odpow[ev[i].ind]=check(ev[i].y)<=ev[i].k;
		else update(ev[i].y,ev[i].k);
	}
	for (ll i = 1; i<=m; i++)cout << odpow[i] << '\n';
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (ll i = 0; i<ev.size(); i++){
      |                 ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 920 KB Output is correct
12 Correct 2 ms 1176 KB Output is correct
13 Correct 3 ms 1176 KB Output is correct
14 Correct 3 ms 1436 KB Output is correct
15 Correct 5 ms 1436 KB Output is correct
16 Correct 2 ms 924 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 3 ms 1180 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 142556 KB Output is correct
2 Correct 703 ms 144916 KB Output is correct
3 Correct 676 ms 144904 KB Output is correct
4 Correct 701 ms 145032 KB Output is correct
5 Correct 484 ms 90228 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13580 KB Output is correct
2 Correct 64 ms 13732 KB Output is correct
3 Correct 41 ms 8140 KB Output is correct
4 Correct 49 ms 8136 KB Output is correct
5 Correct 42 ms 8136 KB Output is correct
6 Correct 43 ms 8616 KB Output is correct
7 Correct 41 ms 8640 KB Output is correct
8 Correct 45 ms 12852 KB Output is correct
9 Correct 27 ms 6892 KB Output is correct
10 Correct 43 ms 12992 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 920 KB Output is correct
12 Correct 2 ms 1176 KB Output is correct
13 Correct 3 ms 1176 KB Output is correct
14 Correct 3 ms 1436 KB Output is correct
15 Correct 5 ms 1436 KB Output is correct
16 Correct 2 ms 924 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 3 ms 1180 KB Output is correct
19 Correct 136 ms 29444 KB Output is correct
20 Correct 126 ms 29540 KB Output is correct
21 Correct 125 ms 29324 KB Output is correct
22 Correct 159 ms 29376 KB Output is correct
23 Correct 140 ms 29332 KB Output is correct
24 Correct 85 ms 18084 KB Output is correct
25 Correct 86 ms 18104 KB Output is correct
26 Correct 97 ms 18340 KB Output is correct
27 Correct 116 ms 18340 KB Output is correct
28 Correct 95 ms 18344 KB Output is correct
29 Correct 101 ms 18596 KB Output is correct
30 Correct 103 ms 18344 KB Output is correct
31 Correct 102 ms 18380 KB Output is correct
32 Correct 125 ms 18340 KB Output is correct
33 Correct 99 ms 18500 KB Output is correct
34 Correct 87 ms 18084 KB Output is correct
35 Correct 84 ms 18092 KB Output is correct
36 Correct 112 ms 17832 KB Output is correct
37 Correct 94 ms 17832 KB Output is correct
38 Correct 112 ms 18084 KB Output is correct
39 Correct 98 ms 27664 KB Output is correct
40 Correct 79 ms 17744 KB Output is correct
41 Correct 98 ms 26276 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 920 KB Output is correct
12 Correct 2 ms 1176 KB Output is correct
13 Correct 3 ms 1176 KB Output is correct
14 Correct 3 ms 1436 KB Output is correct
15 Correct 5 ms 1436 KB Output is correct
16 Correct 2 ms 924 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 3 ms 1180 KB Output is correct
19 Correct 677 ms 142556 KB Output is correct
20 Correct 703 ms 144916 KB Output is correct
21 Correct 676 ms 144904 KB Output is correct
22 Correct 701 ms 145032 KB Output is correct
23 Correct 484 ms 90228 KB Output is correct
24 Correct 63 ms 13580 KB Output is correct
25 Correct 64 ms 13732 KB Output is correct
26 Correct 41 ms 8140 KB Output is correct
27 Correct 49 ms 8136 KB Output is correct
28 Correct 42 ms 8136 KB Output is correct
29 Correct 43 ms 8616 KB Output is correct
30 Correct 41 ms 8640 KB Output is correct
31 Correct 45 ms 12852 KB Output is correct
32 Correct 27 ms 6892 KB Output is correct
33 Correct 43 ms 12992 KB Output is correct
34 Correct 136 ms 29444 KB Output is correct
35 Correct 126 ms 29540 KB Output is correct
36 Correct 125 ms 29324 KB Output is correct
37 Correct 159 ms 29376 KB Output is correct
38 Correct 140 ms 29332 KB Output is correct
39 Correct 85 ms 18084 KB Output is correct
40 Correct 86 ms 18104 KB Output is correct
41 Correct 97 ms 18340 KB Output is correct
42 Correct 116 ms 18340 KB Output is correct
43 Correct 95 ms 18344 KB Output is correct
44 Correct 101 ms 18596 KB Output is correct
45 Correct 103 ms 18344 KB Output is correct
46 Correct 102 ms 18380 KB Output is correct
47 Correct 125 ms 18340 KB Output is correct
48 Correct 99 ms 18500 KB Output is correct
49 Correct 87 ms 18084 KB Output is correct
50 Correct 84 ms 18092 KB Output is correct
51 Correct 112 ms 17832 KB Output is correct
52 Correct 94 ms 17832 KB Output is correct
53 Correct 112 ms 18084 KB Output is correct
54 Correct 98 ms 27664 KB Output is correct
55 Correct 79 ms 17744 KB Output is correct
56 Correct 98 ms 26276 KB Output is correct
57 Correct 708 ms 145684 KB Output is correct
58 Correct 706 ms 145624 KB Output is correct
59 Correct 658 ms 145496 KB Output is correct
60 Correct 726 ms 145476 KB Output is correct
61 Correct 707 ms 145284 KB Output is correct
62 Correct 692 ms 145420 KB Output is correct
63 Correct 444 ms 88956 KB Output is correct
64 Correct 459 ms 88852 KB Output is correct
65 Correct 521 ms 90720 KB Output is correct
66 Correct 495 ms 90724 KB Output is correct
67 Correct 497 ms 90464 KB Output is correct
68 Correct 503 ms 90724 KB Output is correct
69 Correct 488 ms 90724 KB Output is correct
70 Correct 520 ms 90724 KB Output is correct
71 Correct 473 ms 90720 KB Output is correct
72 Correct 497 ms 90464 KB Output is correct
73 Correct 508 ms 87512 KB Output is correct
74 Correct 431 ms 88320 KB Output is correct
75 Correct 447 ms 87396 KB Output is correct
76 Correct 495 ms 87460 KB Output is correct
77 Correct 472 ms 87088 KB Output is correct
78 Correct 573 ms 112228 KB Output is correct
79 Correct 436 ms 107900 KB Output is correct
80 Correct 578 ms 120992 KB Output is correct