Submission #1267841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267841		usukhbaatar	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1235 ms	127488 KiB

sortbooks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define heap priority_queue
#define endl '\n'
#define maxx(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
const int oo ((((1LL << 62) - 1) << 1) + 1);
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

int n, q;
vi a;
vector<array<int, 4>> queries;

pii meta(int i) { return {(i << 1) + 1, (i + 1) << 1}; }
tuple<int, int, int> meta(int i, int l, int r) {
	pii m = meta(i); return { m.ff, m.ss, (l + r) / 2 };
}

vi val;

void update(int i, int tl, int tr, int k, int t) {
	if (tl == tr) { val[i] = t; return; }
	auto [x, y, tm] = meta(i, tl,  tr);
	if (k <= tm) update(x, tl, tm, k, t);
	else update(y, tm + 1, tr, k, t);
	val[i] = max(val[x], val[y]);
}

int query(int i, int tl, int tr, int l, int r) {
	if (tl == l && r == tr) return val[i];
	auto [x, y, tm] = meta(i, tl, tr);
	if (r <= tm) return query(x, tl, tm, l, r);
	else if (tm + 1 <= l) return query(y, tm + 1, tr, l, r);
	return max(query(x, tl, tm, l, tm), query(y, tm + 1, tr, tm + 1, r));
}


int32_t main() {
	fastio;
	cin >> n >> q;
	a.resize(n + 1); a[0] = 1e10;
	vi stk = {0};
	rep1(i, n) {
		cin >> a[i];
		while(a[stk.back()] <= a[i]) stk.pop_back();
		if (stk.size() > 1) {
			queries.pb({-a[i] - a[stk.back()], 1, i, stk.back()});
		}
		stk.pb(i);
	}
	vi ans(q);
	vi l(q), r(q);
	rep(i, q) {
		int k;
		cin >> l[i] >> r[i] >> k;
		queries.pb({-k, 0, i, 0});
	}
	sort(all(queries));
	val.resize(4 * n);

	for (auto &qry : queries) {
		//cout << qry[0] << ' ' << qry[1] << ' ' << qry[2] << ' ' << qry[3] << endl;
		if (qry[1] == 1) update(0, 0, n - 1, qry[2] - 1, qry[3]);
		else {
			int id = qry[2];
			ans[id] = (query(0, 0, n - 1, l[id] - 1, r[id] - 1) > l[id] ? 0 : 1);
		}
	}
	for (int x : ans) cout << x << endl;
	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