oj.uz

Submission #959804

# Submission time Handle Problem Language Result Execution time Memory
959804 2024-04-09T06:48:57 Z pcc Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 879 ms 53496 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>


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
	struct node{
		int mx,mn;
		int val;
		node(){mx = 0,mn = 0,val = 0;}
	};
	node seg[mxn*4];
	SEG(){
		for(auto &i:seg)i = node();
	}
	node pull(node a,node b){
		node re;
		re.mx = max(a.mx,b.mx);
		re.mn = min(a.mn,b.mn);
		re.val = max({a.val,b.val,a.mx-b.mn});
		return re;
	}
	void build(int now,int l,int r){
		if(l == r){
			seg[now].mx = seg[now].mn = arr[l];
			seg[now].val = 0;
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	node getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
#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).val;
		cout<<(re<=v)<<'\n';
	}
	return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 53132 KB Output is correct
2 Incorrect 866 ms 53496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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