Submission #883815

#	Time	Username	Problem	Language	Result	Execution time	Memory
883815		serifefedartar	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1715 ms	111040 KiB

sortbooks

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 +  100;

struct Node {
	int ans, mx_pos;
	Node() { }
	Node(int _ans, int _mx_pos) : ans(_ans), mx_pos(_mx_pos) { }
}; 

vector<pair<pair<int,int>,int>> v[MAXN];
vector<int> w;
Node sg[4 * MAXN];
int lazy[MAXN], ans[MAXN];

Node merge(Node A, Node B) {
	Node new_node;
	new_node.ans = max(A.ans, B.ans);
	new_node.mx_pos = max(A.mx_pos, B.mx_pos);
	return new_node;
}

void push(int k, int a, int b) {
	sg[k].ans = max(sg[k].ans, sg[k].mx_pos - lazy[k]);
	if (a != b) {
		lazy[2*k] = min(lazy[2*k], lazy[k]);
		lazy[2*k+1] = min(lazy[2*k+1], lazy[k]);
	}
	lazy[k] = 1e9 + 1000;
}

void init(int k, int a, int b) {
	if (a == b) {
		sg[k].ans = 0;
		sg[k].mx_pos = w[a];
		lazy[k] = 1e9 + 1000;
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
	lazy[k] = 1e9 + 1000;
}

void update(int k, int a, int b, int q_l, int q_r, int val) {
	push(k, a, b);
	if (b < q_l || a > q_r)
		return ;
	if (q_l <= a && b <= q_r) {
		lazy[k] = val;
		push(k, a, b);
		return ;
	}
	update(2*k, a, (a+b)/2, q_l, q_r, val);
	update(2*k+1, (a+b)/2+1, b, q_l, q_r, val);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

Node query(int k, int a, int b, int q_l, int q_r) {
	push(k, a, b);
	if (b < q_l || a > q_r)
		return Node(-1, -1);
	if (q_l <= a && b <= q_r)
		return sg[k];
	return merge(query(2*k, a, (a+b)/2, q_l, q_r), query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

int main() {
	fast
	int N, M, l, r, k;
	cin >> N >> M;

	w = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> w[i];
	for (int i = 0; i < M; i++) {
		cin >> l >> r >> k;
		v[r].push_back({{l, k}, i});
	}
	init(1, 1, N);

	for (int i = 1; i <= N; i++) {
		update(1, 1, N, 1, i, w[i]);
		for (auto u : v[i]) {
			int Q = query(1, 1, N, u.f.f, i).ans;
			if (Q > u.f.s)
				ans[u.s] = 0;
			else
				ans[u.s] = 1;
		}
	}

	for (int i = 0; i < M; i++)
		cout << ans[i] << "\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