Submission #1236689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236689		pvb.tunglam	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	438 ms	70516 KiB

sortbooks

#include <bits/stdc++.h>
#define hash _hash_ 
#define y1 _y1_
#define left _left_ 
#define right _right_
#define dec _dec_   	
using namespace std;

using ll = long long;
using ull = unsigned long long;

	/*----------- I alone decide my fate! ------------*/
/*  I just do what I gotta, in the heat of the summer...  */

int N, Q, a[1000009], st[1000009], lef[1000009];
vector <int> pos[1000009];
struct query {
	int l, r, k, idx;
} q[1000009];
bool res[1000009];

int bit[1000009];
void update(int x, int val) {
	while (x <= 1000000) {
		bit[x] = max(bit[x], val);
		x += x &- x;
	}
}

int get(int x) {
	int ret = 0;
	while (x) {
		ret= max(ret, bit[x]);
		x -= x &- x;
	}
	return ret;
}

void solve() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i ++) {
		cin >> a[i];
	}
	int top = 0;
	for (int i = 1; i <= N; i ++) {
		while (top > 0 && a[i] >= a[st[top]]) top--;
		lef[i] = st[top];
		pos[st[top]].push_back(i);
		st[++top] = i;
	}
	for (int i = 1; i <= Q; i ++) {
		cin >> q[i].l >> q[i].r >> q[i].k;
		q[i].idx = i;
	}
	sort(q + 1, q + Q + 1, [] (query x, query y) {
		return x.l > y.l;
	});
	int pt = N;
	for (int i = 1; i <= Q; i ++) {
		while (pt >= q[i].l) {
			for (auto x : pos[pt]) update(x, a[x] + a[pt]);
			pt --;
		}
		res[q[i].idx] = (get(q[i].r) <= q[i].k);
	}
	for (int i = 1; i <=Q; i ++) {
		cout << res[i] << "\n";
	}
} 	


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();
}


/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Cant wake up? Wake me up inside
*/

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