Submission #837091

#	Time	Username	Problem	Language	Result	Execution time	Memory
837091		MODDI	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	328 ms	88564 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int MXN = 1e5 + 10;
	int n;
	vector<pii> tree;
	vi arr;
	int lg[MXN+1];
		
	int table[20][MXN];
	void init(int _n, vi _arr){
		n = _n;
		tree.resize(4*n);
		arr = _arr;
		lg[1] = 0;
		for(int i = 2; i <= MXN; i++)	lg[i] = lg[i/2] + 1;	
		copy(arr.begin(), arr.end(), table[0]);
		for(int i = 1; i <= lg[n]; i++){
			for(int j = 0; j + (1 << i) <= n; j++){
				table[i][j] = max(table[i-1][j], table[i-1][j + (1 << (i-1))]);
			}
		}
	}
	int query_table(int l, int r){
		int i = lg[r-l+1];
		return max(table[i][l], table[i][r - (1 << i) +1]);
	}
	void build(int node, int l, int r){
		if(l == r)	tree[node] = mp(arr[l], l);
		else{
			int mid = (l + r) / 2;
			build(node*2, l, mid);
			build(node*2+1, mid+1, r);
			tree[node] = max(tree[node*2], tree[node*2+1]);
		}
	}
	pii query(int node, int l, int r, int L, int R){
		if(r < L || l > R)	return mp(0,0);
		if(L <= l && r <= R){
			if(query_table(L, tree[node].second-1) < tree[node].first)
				return mp(0,0);
			return mp(tree[node].first + query_table(L, tree[node].second-1), tree[node].second);
		}
		int mid = (l + r) / 2;
		pii left = query(node*2, l, mid, L, R);
		pii right = query(node*2+1, mid+1, r, L, R);
		return max(left, right);
	}
int main(){
	int n, m;
	cin>>n>>m;
	arr.resize(n);
	for(int i = 0; i < n; i++)	cin>>arr[i];
	init(n, arr);
	build(1, 0, n-1);
	while(m--){
		int l, r, k;
		cin>>l>>r>>k;
		l--; r--;
		pii here = query(1, 0, n-1, l, r);
		if(here.first > k)	cout<<0<<"\n";
		else cout<<1<<"\n";
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23