Submission #1156319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156319		Jawad_Akbar_JJ	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1188 ms	108460 KiB

sortbooks

#include <iostream>
#include <vector>

using namespace std;
const int N = (1<<20) + 1;
int seg[N<<1], a[N], Ans[N], x[N];
vector<int> nxt[N], vec;
vector<pair<int, int>> Vec[N];

void insert(int i, int vl, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		seg[cur] = vl;
		return;
	}

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, vl, lc, st, mid);
	insert(i, vl, rc, mid, en);
	seg[cur] = max(seg[lc], seg[rc]);
}

int get(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st) return 0;
	if (l <= st and r >= en) return seg[cur];

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m;
	cin>>n>>m;

	for (int i=1;i<=n;i++)
		cin>>a[i];

	for (int i=n;i>=1;i--){
		while (vec.size() > 0 and a[vec.back()] < a[i]){
			nxt[i].push_back(vec.back());
			insert(vec.back(), a[vec.back()] + a[i]);
			vec.pop_back();
		}
		vec.push_back(i);
	}

	for (int i=1;i<=m;i++){
		int l, r;
		cin>>l>>r>>x[i];
		Vec[l].push_back({r + 1, i});
	}

	for (int i=1;i<=n;i++){
		for (auto [r, id] : Vec[i]){
			if (get(i, r) <= x[id])
				Ans[id] = 1;
		}

		for (int j : nxt[i])
			insert(j, 0);
	}

	for (int i=1;i<=m;i++)
		cout<<Ans[i]<<'\n';
}

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