oj.uz

Submission #959842

# Submission time Handle Problem Language Result Execution time Memory
959842 2024-04-09T08:06:17 Z pcc Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 261268 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

const int mxn = 1e6+10;
int arr[mxn];
int N,Q;

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	int val[mxn*4];
	int mx[mxn*4];
	vector<int> seg[mxn*4];
	SEG(){}
	void build(int now,int l,int r){
		for(int i = l;i<=r;i++)seg[now].push_back(arr[i]);
		sort(seg[now].begin(),seg[now].end());
		mx[now] = seg[now].back();
		if(l == r)return;
		build(ls,l,mid);
		build(rs,mid+1,r);
		val[now] = max(val[ls],val[rs]);
		if(seg[rs].back()<seg[ls].back())val[now] = max(val[now],seg[ls].back()+seg[rs].back());
		else{
			auto lp = lower_bound(seg[rs].begin(),seg[rs].end(),seg[ls].back());
			if(lp != seg[rs].begin())val[now] = max(val[now],seg[ls].back()+*prev(lp));
		}
		return;
	}
	pii getval(int now,int l,int r,int s,int e,int big = 0){
		if(l>=s&&e>=r){
			pii re;
			re.fs = val[now];
			if(seg[now].back()<big)re.fs = max(re.fs,big+seg[now].back());
			else{
				auto lp = lower_bound(seg[now].begin(),seg[now].end(),big);
				if(lp != seg[now].begin())re.fs = max(re.fs,big+*prev(lp));
			}
			re.sc = max(big,mx[now]);
			return re;
		}
		if(mid>=e)return getval(ls,l,mid,s,e,big);
		else if(mid<s)return getval(rs,mid+1,r,s,e,big);
		else{
			auto re = getval(ls,l,mid,s,e,big);
			auto tmp = getval(rs,mid+1,r,s,e,re.sc);
			return pii(max(re.fs,tmp.fs),max(re.sc,tmp.sc));
		}
	}
#undef ls
#undef rs 
#undef mid
};

SEG seg;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	seg.build(0,1,N);
	while(Q--){
		int s,e,v;
		cin>>s>>e>>v;
		int re = seg.getval(0,1,N,s,e).fs;
		cout<<(re<=v)<<'\n';
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 96796 KB Output is correct
2 Correct 21 ms 96856 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 23 ms 96860 KB Output is correct
5 Correct 25 ms 96856 KB Output is correct
6 Correct 22 ms 96856 KB Output is correct
7 Correct 23 ms 96856 KB Output is correct
8 Correct 22 ms 96860 KB Output is correct
9 Correct 22 ms 96856 KB Output is correct
10 Correct 22 ms 97112 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 96796 KB Output is correct
2 Correct 21 ms 96856 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 23 ms 96860 KB Output is correct
5 Correct 25 ms 96856 KB Output is correct
6 Correct 22 ms 96856 KB Output is correct
7 Correct 23 ms 96856 KB Output is correct
8 Correct 22 ms 96860 KB Output is correct
9 Correct 22 ms 96856 KB Output is correct
10 Correct 22 ms 97112 KB Output is correct
11 Correct 25 ms 97116 KB Output is correct
12 Correct 28 ms 97628 KB Output is correct
13 Correct 27 ms 97620 KB Output is correct
14 Correct 28 ms 97584 KB Output is correct
15 Correct 28 ms 97628 KB Output is correct
16 Correct 29 ms 97624 KB Output is correct
17 Correct 25 ms 97368 KB Output is correct
18 Correct 26 ms 97580 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3101 ms 261268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 115640 KB Output is correct
2 Correct 194 ms 115876 KB Output is correct
3 Correct 161 ms 115916 KB Output is correct
4 Correct 164 ms 115924 KB Output is correct
5 Correct 160 ms 115924 KB Output is correct
6 Correct 128 ms 115908 KB Output is correct
7 Correct 127 ms 114128 KB Output is correct
8 Correct 131 ms 115596 KB Output is correct
9 Correct 52 ms 98132 KB Output is correct
10 Correct 130 ms 113832 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 96796 KB Output is correct
2 Correct 21 ms 96856 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 23 ms 96860 KB Output is correct
5 Correct 25 ms 96856 KB Output is correct
6 Correct 22 ms 96856 KB Output is correct
7 Correct 23 ms 96856 KB Output is correct
8 Correct 22 ms 96860 KB Output is correct
9 Correct 22 ms 96856 KB Output is correct
10 Correct 22 ms 97112 KB Output is correct
11 Correct 25 ms 97116 KB Output is correct
12 Correct 28 ms 97628 KB Output is correct
13 Correct 27 ms 97620 KB Output is correct
14 Correct 28 ms 97584 KB Output is correct
15 Correct 28 ms 97628 KB Output is correct
16 Correct 29 ms 97624 KB Output is correct
17 Correct 25 ms 97368 KB Output is correct
18 Correct 26 ms 97580 KB Output is correct
19 Correct 507 ms 131044 KB Output is correct
20 Correct 492 ms 131056 KB Output is correct
21 Correct 390 ms 133076 KB Output is correct
22 Correct 390 ms 133068 KB Output is correct
23 Correct 383 ms 132944 KB Output is correct
24 Correct 276 ms 131796 KB Output is correct
25 Correct 283 ms 131828 KB Output is correct
26 Correct 347 ms 133056 KB Output is correct
27 Correct 346 ms 133124 KB Output is correct
28 Correct 386 ms 133068 KB Output is correct
29 Correct 384 ms 132964 KB Output is correct
30 Correct 399 ms 133072 KB Output is correct
31 Correct 388 ms 133000 KB Output is correct
32 Correct 398 ms 132956 KB Output is correct
33 Correct 427 ms 133072 KB Output is correct
34 Correct 268 ms 131788 KB Output is correct
35 Correct 268 ms 132816 KB Output is correct
36 Correct 270 ms 132940 KB Output is correct
37 Correct 265 ms 132676 KB Output is correct
38 Correct 274 ms 133064 KB Output is correct
39 Correct 357 ms 132224 KB Output is correct
40 Correct 232 ms 118280 KB Output is correct
41 Correct 307 ms 131948 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 96796 KB Output is correct
2 Correct 21 ms 96856 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 23 ms 96860 KB Output is correct
5 Correct 25 ms 96856 KB Output is correct
6 Correct 22 ms 96856 KB Output is correct
7 Correct 23 ms 96856 KB Output is correct
8 Correct 22 ms 96860 KB Output is correct
9 Correct 22 ms 96856 KB Output is correct
10 Correct 22 ms 97112 KB Output is correct
11 Correct 25 ms 97116 KB Output is correct
12 Correct 28 ms 97628 KB Output is correct
13 Correct 27 ms 97620 KB Output is correct
14 Correct 28 ms 97584 KB Output is correct
15 Correct 28 ms 97628 KB Output is correct
16 Correct 29 ms 97624 KB Output is correct
17 Correct 25 ms 97368 KB Output is correct
18 Correct 26 ms 97580 KB Output is correct
19 Execution timed out 3101 ms 261268 KB Time limit exceeded
20 Halted 0 ms 0 KB -