Submission #1177613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177613		drakozs	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1078 ms	241164 KiB

sortbooks

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define MOD 1000000007
#define MAXN 2e5
#define SIZE 20
#define pb push_back

using namespace std;

ll power(ll a, ll b){
	if (b == 0) return 1;
	ll res = power(a, b / 2);
//	if (b % 2 == 1) return res * res % MOD * a % MOD;
//	return res * res % MOD;
	
	if (b % 2 == 1) return res * res * a;
	return res * res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<int> nums(n + 1);
	for (int i = 1; i <= n; i++) cin >> nums[i];
	vector<vector<int>> minArr(n + 1, vector<int>(SIZE)), maxArr(n + 1, vector<int>(SIZE));
	for (int i = 1; i <= n; i++){
		minArr[i][0] = nums[i];
		maxArr[i][0] = nums[i];
	}
//	cout << "AAA\n";
	for (int j = 1; j < SIZE; j++){
		for (int i = 1; i <= n; i++){
			int len = i + power(2, j) - 1;
			if (len > n) break;
			int pos = i + power(2, j - 1);
//			cout << i << ", " << pos << "\n";
			minArr[i][j] = min(minArr[i][j - 1], minArr[pos][j - 1]);
			maxArr[i][j] = max(maxArr[i][j - 1], maxArr[pos][j - 1]);
		}
	}
//	cout << "AAA\n";
//	for (int i = 1; i <= n; i++){
//		cout << minArr[i][1] << "\n";
//	}
	while(m--){
		int l, r, d;
		cin >> l >> r >> d;
		int amount = log2(r - l + 1);
		int minNum = min(minArr[l][amount], minArr[r - power(2, amount) + 1][amount]);
		int maxNum = max(maxArr[l][amount], maxArr[r - power(2, amount) + 1][amount]);
//		cout << maxNum << ", " << minNum << " aaa\n";
		if (maxNum + minNum <= d) cout << "1\n";
		else cout << "0\n";
	}
	
	
	return 0;
}

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