oj.uz

Submission #998422

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

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,sega;

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));
	}
	vector<int>v;
	for(int i=n;i>=1;i--){
		while((int)v.size()>0&&all[i]>all[v.back()]){
			v.pop_back();
		}
		if((int)v.size()>0){
			tr[i]=v.back();
		}else{
			tr[i]=n+1;
		}
		v.push_back(i);
	}
	for(int i=1;i<=n;i++){
		sega.ins(i,make_pair(all[i]+seg.pors(1,0,kaf-1,i+1,tr[i]-1).first,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){
		pair<int,int>pp=seg.pors(1,0,kaf-1,p.second+1,r);
		if(p.first+pp.first>w){
			return 0;
		}
	}
	if(p.second==l){
		return 1;
	}
	return sega.pors(1,0,kaf-1,l,p.second-1).first<=w;
}

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

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1139 ms 72004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 6576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -