oj.uz

Submission #998417

# Submission time Handle Problem Language Result Execution time Memory
998417 2024-06-14T00:34:41 Z amirhoseinfar1385 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 55140 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int all[maxn],n,q,kaf=(1<<20);

struct segment{
	pair<int,int>seg[(1<<21)];
	void ins(int i,pair<int,int>w){
		i+=kaf;
		while(i>0){
			seg[i]=max(seg[i],w);
			i>>=1;
		}
	}
	pair<int,int>pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return make_pair(0,0);
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seg;

void vorod(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
}

void pre(){
	for(int i=1;i<=n;i++){
		seg.ins(i,make_pair(all[i],i));
	}
}

int calc(int l,int r,int w){
	if(l>r){
		return 1;
	}
	pair<int,int>p=seg.pors(1,0,kaf-1,l,r);
	if(p.second==r){
		return calc(l,r-1,w);
	}
	pair<int,int>pp=seg.pors(1,0,kaf-1,p.second+1,r);
	if(p.first+pp.first>w){
		return 0;
	}
	return (calc(l,p.second-1,w)&calc(p.second+1,r,w));
}

void solve(){
	for(int i=0;i<q;i++){
		int l,r,w;
		cin>>l>>r>>w;
		cout<<calc(l,r,w)<<endl;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	vorod();
	pre();
	solve();
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 18 ms 348 KB Output is correct
9 Correct 6 ms 2392 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 14 ms 788 KB Output is correct
15 Correct 11 ms 2652 KB Output is correct
16 Correct 1840 ms 712 KB Output is correct
17 Correct 916 ms 604 KB Output is correct
18 Correct 260 ms 680 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 54188 KB Output is correct
2 Correct 2051 ms 55120 KB Output is correct
3 Correct 2159 ms 55084 KB Output is correct
4 Correct 2173 ms 55140 KB Output is correct
5 Execution timed out 3035 ms 30388 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 18 ms 348 KB Output is correct
9 Correct 6 ms 2392 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 14 ms 788 KB Output is correct
15 Correct 11 ms 2652 KB Output is correct
16 Correct 1840 ms 712 KB Output is correct
17 Correct 916 ms 604 KB Output is correct
18 Correct 260 ms 680 KB Output is correct
19 Execution timed out 3029 ms 6488 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 18 ms 348 KB Output is correct
9 Correct 6 ms 2392 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 14 ms 788 KB Output is correct
15 Correct 11 ms 2652 KB Output is correct
16 Correct 1840 ms 712 KB Output is correct
17 Correct 916 ms 604 KB Output is correct
18 Correct 260 ms 680 KB Output is correct
19 Correct 2041 ms 54188 KB Output is correct
20 Correct 2051 ms 55120 KB Output is correct
21 Correct 2159 ms 55084 KB Output is correct
22 Correct 2173 ms 55140 KB Output is correct
23 Execution timed out 3035 ms 30388 KB Time limit exceeded
24 Halted 0 ms 0 KB -