Submission #249864

#	Time	Username	Problem	Language	Result	Execution time	Memory
249864		minhcool	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1713 ms	262144 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

int n, q, w[1000005], sparse1[1000005][20], sparse2[1000005][20], sparse3[1000005][20];

int mx1(int l, int r){
	int k = log2(r - l + 1);
	return max(sparse1[l][k], sparse1[r - (1 << k) + 1][k]);
}

int mx2(int l, int r){
	int k = log2(r - l + 1);
	return max(sparse2[l][k], sparse2[r - (1 << k) + 1][k]);
}

int mn(int l, int r){
	int k = log2(r - l + 1);
	return min(sparse3[l][k], sparse3[r - (1 << k) + 1][k]);
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> w[i];
		sparse1[i][0] = sparse3[i][0] = w[i];
		//cout << w[i] << "\n";
	}
	for(int i = 1; i <= 20; i++){
		for(int j = 1; j <= (n - (1 << i) + 1); j++){
			sparse1[j][i] = max(sparse1[j][i - 1], sparse1[j + (1 << (i - 1))][i - 1]);
			//cout << i << " " << j << " " << sparse1[j][i] << "\n";
		}
	}
	for(int i = 1; i <= 20; i++){
		for(int j = 1; j <= (n - (1 << i) + 1); j++) sparse3[j][i] = min(sparse3[j][i - 1], sparse3[j + (1 << (i - 1))][i - 1]);
	}
	for(int i = 1; i <= n; i++){
		int l = 1, r = i;
		while(l < (r - 1)){
			int mid = (l + r) >> 1;
			if(mx1(mid, i) == w[i]) r = mid;
			else l = mid;
		}
		while(mx1(l, i) > w[i]) l++;
		sparse2[i][0] = l;
	}
	for(int i = 1; i <= 20; i++){
		for(int j = 1; j <= (n - (1 << i) + 1); j++) sparse2[j][i] = max(sparse2[j][i - 1], sparse2[j + (1 << (i - 1))][i - 1]);\
	}
	while(q--){
		int l, r, k;
		cin >> l >> r >> k;
		int l1 = l, r1 = r;
		while(l1 < (r1 - 1)){
			int mid = (l1 + r1) >> 1;
			if(mx2(mid, r) > l) l1 = mid;
			else r1 = mid;
		}
		while(l1 <= r && mx2(l1, r) > l) l1++;
		l1--;
		if(l1 == l){
			cout << 1 << "\n";
			continue;
		}
		//cout << mx1(l, l1) << " " << mn(l, l1) << "\n";
		cout << (k >= (mx1(l, l1) + mn(l, l1))) << "\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