Submission #351890

#	Time	Username	Problem	Language	Result	Execution time	Memory
351890		cheissmart	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	2759 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define debu(x) cerr << #x << " is " << x << ", "

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

int a[N], ans[N], mx[N][20], mn[N][20];
V<array<int, 3>> G[N];

signed main()
{
	IO_OP;

	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		mx[i][0] = mn[i][0] = a[i];
	}
	for(int j = 1; j < 20; j++) {
		for(int i = 0; i + (1 << j) - 1 < n; i++) {
			mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
			mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
		}
	}
	auto qmx = [&] (int l, int r) {
		int k = __lg(r - l + 1);
		return max(mx[l][k], mx[r - (1 << k) + 1][k]);	
	};
	auto qmn = [&] (int l, int r) {
		int k = __lg(r - l + 1);
		return min(mn[l][k], mn[r - (1 << k) + 1][k]);	
	};
	for(int i = 0; i < m; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		l--, r--;
		G[l].PB({r, k, i});
	}
	set<int> one_pos;
	priority_queue<pi, V<pi>, greater<pi>> zeros; // (val, pos)
	for(int i = n - 1; i >= 0; i--) {
		zeros.push({a[i], i});
		while(zeros.top().F < a[i]) {
			int pos = zeros.top().S;
			zeros.pop();
			one_pos.insert(pos);
		}
		for(auto qq:G[i]) {
			int r = qq[0], k = qq[1], qi = qq[2];
			auto it = one_pos.upper_bound(r);
			if(it == one_pos.begin()) {
				ans[qi] = 1;
			} else {
				r = *prev(it);
				if(qmx(i, r) + qmn(i, r) <= k) ans[qi] = 1;
				else ans[qi] = 0;
			}
		}
	}

	for(int i = 0; i < m; i++)
		cout << ans[i] << '\n';

}

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