oj.uz

Submission #959807

# Submission time Handle Problem Language Result Execution time Memory
959807 2024-04-09T07:03:28 Z pcc Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 246272 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]);
		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];
			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 58 ms 96880 KB Output is correct
2 Correct 23 ms 96800 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 22 ms 96852 KB Output is correct
5 Correct 22 ms 96860 KB Output is correct
6 Correct 24 ms 96944 KB Output is correct
7 Correct 24 ms 96944 KB Output is correct
8 Correct 23 ms 96860 KB Output is correct
9 Correct 24 ms 96848 KB Output is correct
10 Correct 24 ms 96860 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 96880 KB Output is correct
2 Correct 23 ms 96800 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 22 ms 96852 KB Output is correct
5 Correct 22 ms 96860 KB Output is correct
6 Correct 24 ms 96944 KB Output is correct
7 Correct 24 ms 96944 KB Output is correct
8 Correct 23 ms 96860 KB Output is correct
9 Correct 24 ms 96848 KB Output is correct
10 Correct 24 ms 96860 KB Output is correct
11 Correct 24 ms 97116 KB Output is correct
12 Correct 27 ms 97624 KB Output is correct
13 Correct 27 ms 97628 KB Output is correct
14 Correct 29 ms 97624 KB Output is correct
15 Correct 28 ms 97672 KB Output is correct
16 Correct 27 ms 97652 KB Output is correct
17 Correct 28 ms 97380 KB Output is correct
18 Correct 27 ms 97624 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 114604 KB Output is correct
2 Correct 199 ms 116724 KB Output is correct
3 Correct 160 ms 116692 KB Output is correct
4 Correct 155 ms 116692 KB Output is correct
5 Correct 165 ms 116728 KB Output is correct
6 Correct 125 ms 116432 KB Output is correct
7 Correct 130 ms 116432 KB Output is correct
8 Correct 164 ms 116388 KB Output is correct
9 Correct 61 ms 98324 KB Output is correct
10 Correct 137 ms 116248 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 96880 KB Output is correct
2 Correct 23 ms 96800 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 22 ms 96852 KB Output is correct
5 Correct 22 ms 96860 KB Output is correct
6 Correct 24 ms 96944 KB Output is correct
7 Correct 24 ms 96944 KB Output is correct
8 Correct 23 ms 96860 KB Output is correct
9 Correct 24 ms 96848 KB Output is correct
10 Correct 24 ms 96860 KB Output is correct
11 Correct 24 ms 97116 KB Output is correct
12 Correct 27 ms 97624 KB Output is correct
13 Correct 27 ms 97628 KB Output is correct
14 Correct 29 ms 97624 KB Output is correct
15 Correct 28 ms 97672 KB Output is correct
16 Correct 27 ms 97652 KB Output is correct
17 Correct 28 ms 97380 KB Output is correct
18 Correct 27 ms 97624 KB Output is correct
19 Correct 563 ms 135996 KB Output is correct
20 Correct 539 ms 136188 KB Output is correct
21 Correct 408 ms 135800 KB Output is correct
22 Correct 445 ms 135876 KB Output is correct
23 Correct 401 ms 135888 KB Output is correct
24 Correct 303 ms 135648 KB Output is correct
25 Correct 275 ms 135628 KB Output is correct
26 Correct 390 ms 135952 KB Output is correct
27 Correct 404 ms 135816 KB Output is correct
28 Correct 405 ms 136036 KB Output is correct
29 Correct 389 ms 136048 KB Output is correct
30 Correct 422 ms 135868 KB Output is correct
31 Correct 391 ms 136100 KB Output is correct
32 Correct 400 ms 136152 KB Output is correct
33 Correct 401 ms 135868 KB Output is correct
34 Correct 307 ms 135516 KB Output is correct
35 Correct 269 ms 135584 KB Output is correct
36 Correct 265 ms 135408 KB Output is correct
37 Correct 264 ms 135452 KB Output is correct
38 Correct 269 ms 135536 KB Output is correct
39 Correct 376 ms 134640 KB Output is correct
40 Correct 223 ms 121780 KB Output is correct
41 Correct 352 ms 134180 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 96880 KB Output is correct
2 Correct 23 ms 96800 KB Output is correct
3 Correct 22 ms 96856 KB Output is correct
4 Correct 22 ms 96852 KB Output is correct
5 Correct 22 ms 96860 KB Output is correct
6 Correct 24 ms 96944 KB Output is correct
7 Correct 24 ms 96944 KB Output is correct
8 Correct 23 ms 96860 KB Output is correct
9 Correct 24 ms 96848 KB Output is correct
10 Correct 24 ms 96860 KB Output is correct
11 Correct 24 ms 97116 KB Output is correct
12 Correct 27 ms 97624 KB Output is correct
13 Correct 27 ms 97628 KB Output is correct
14 Correct 29 ms 97624 KB Output is correct
15 Correct 28 ms 97672 KB Output is correct
16 Correct 27 ms 97652 KB Output is correct
17 Correct 28 ms 97380 KB Output is correct
18 Correct 27 ms 97624 KB Output is correct
19 Execution timed out 3035 ms 246272 KB Time limit exceeded
20 Halted 0 ms 0 KB -