Submission #684222

#	Time	Username	Problem	Language	Result	Execution time	Memory
684222		gagik_2007	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2368 ms	142900 KiB

sortbooks

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1000007;
ll n, m, k;
ll a[N];
ll lst[N];
ll val[N];
vector<int>d[N];
ll t[4 * N];
vector<pair<pair<int, int>, pair<ll, int>>>q;

void update(int v, int tl, int tr, int ind, ll vl) {
	if (tl == tr) {
		t[v] = vl;
	}
	else {
		int tm = (tl + tr) / 2;
		if (ind <= tm) {
			update(2 * v, tl, tm, ind, vl);
		}
		else update(2 * v + 1, tm + 1, tr, ind, vl);
		t[v] = max(t[2 * v], t[2 * v + 1]);
	}
}

ll get_max(int v, int tl, int tr, int l, int r) {
	//cout << v << " " << tl << " " << tr << " " << l << " " << r << endl;
	if (l > r)return 0;
	if (tl == l && tr == r)return t[v];
	else {
		int tm = (tl + tr) / 2;
		return max(get_max(2 * v, tl, tm, l, min(r, tm)),
			get_max(2 * v + 1, tm + 1, tr, max(tm + 1, l), r));
	}
}

void calc_lst() {
	stack<pair<ll, int>>st;
	for (int i = n - 1; i >= 0; i--) {
		pair<ll, int>pr = make_pair(a[i], 0);
		while (!st.empty() && st.top() < pr) {
			lst[st.top().ss] = i;
			st.pop();
		}
		st.push({ a[i],i });
	}
	while (!st.empty()) {
		lst[st.top().ss] = -1;
		st.pop();
	}
}

void calc_val() {
	//cout << "lst: ";
	for (int i = 0; i < n; i++) {
		//cout << lst[i] << " ";
		if (lst[i] == -1)val[i] = 0;
		else val[i] = a[i] + a[lst[i]];
	}
	//cout << endl;
}

void calc_d() {
	for (int i = 0; i < n; i++) {
		if (lst[i] != -1) {
			d[lst[i]].push_back(i);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cin >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	calc_lst();
	calc_val();
	calc_d();
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r >> k;
		l--, r--;
		q.push_back({ {l,r},{k,i} });
	}
	sort(q.begin(), q.end());
	reverse(q.begin(), q.end());
	vector<int>ans(m);
	int qi = 0;
	for (int i = n - 1; i >= 0; i--) {
		//cout << "FINDING NUMBERS FOR WHICH lst[i] == " << i << endl;
		for (auto j : d[i]) {
			//cout << "UPDATING: " << j << endl;
			update(1, 0, n - 1, j, val[j]);
		}
		while (qi < m && q[qi].ff.ff == i) {
			//cout << "ANSWERING: " << q[qi].ss.ss << endl;
			ll res = get_max(1, 0, n - 1, q[qi].ff.ff, q[qi].ff.ss);
			ans[q[qi].ss.ss] = (q[qi].ss.ff >= res);
			qi++;
		}
	}
	for (auto x : ans) {
		cout << x << endl;
	}
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

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