Submission #880990

#	Time	Username	Problem	Language	Result	Execution time	Memory
880990		dubabuba	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3089 ms	47956 KiB

sortbooks

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

typedef vector<int> vi;
void ono_max(int &MAX, int CMP) { if(CMP > MAX) MAX = CMP;}
void ono_min(int &MIN, int CMP) { if(CMP < MIN) MIN = CMP;}

int merge(
	vi &edit, const int &st, const int &en,
	const vi &L, const int &L_st, const int &L_en,
	const vi &R, const int &R_st, const int &R_en) {
	int ret = 0;

	int cur_L = L_st, cur_R = R_st;
	for(int i = st; i <= en; i++) {
		if(cur_L == L_en + 1) {
			edit[i] = R[cur_R];
			cur_R++;
			continue;
		}

		if(cur_R == R_en + 1) {
			edit[i] = L[cur_L];
			cur_L++;
			continue;
		}

		if(L[cur_L] <= R[cur_R]) {
			edit[i] = L[cur_L];
			cur_L++;
		}
		else {
			edit[i] = R[cur_R];
			ono_max(ret, R[cur_R]);
			cur_R++;
		}
	}
	return ret;
}

const int mxl = 25;
const int mxn = 2e5 + 10;
vector<vi> sus(mxl, vi (mxn));
vector<vi> tmp(mxl, vi (mxn));
vi a(mxn), t(mxn);
int n, m;


struct tree {
	int tl, tr;
	int mxx, ans;
	vi &range = t;

	tree *LC, *RC;

	tree() {tl = tr = 0, mxx = ans = 0;}
	tree(int lvl, int l, int r) {
		tl = l, tr = r;
		range = sus[lvl];
		ans = mxx = 0;
	}

	friend tree *comb(const tree *L, const tree *R) {
		tree *ret = new tree();
		ret-> ans = max(L-> ans, R-> ans);
		ret-> mxx = max(L-> mxx, R-> mxx);
		ret-> tl = L-> tl;
		ret-> tr = R-> tr;

		int q = merge(
				ret->range, L-> tl, R-> tr,
				L-> range, L-> tl, L-> tr,
				R-> range, R-> tl, R-> tr
			);
		if(q != 0) ono_max(ret-> ans, L-> mxx + q);
		return ret;
	}

	void build(int lvl) {
		if(tl == tr) {
			ans = range[tl] = a[tl];
			mxx = 0;
			return;
		}

		LC = new tree(lvl + 1, tl, (tl + tr) / 2);
		RC = new tree(lvl + 1, (tl + tr) / 2 + 1, tr);
		LC-> build(lvl + 1);
		RC-> build(lvl + 1);

		tree *buba = comb(LC, RC);
		ans = buba-> ans;
		mxx = buba-> mxx;
	}

	tree *query(int l, int r) {
		if(tl == l && r == tr) return this;
		if(r <= LC-> tr) return LC-> query(l, r);
		if(RC-> tl <= l) return RC-> query(l, r);

		tree *L_qr = LC-> query(l, LC-> tr);
		tree *R_qr = RC-> query(RC-> tl, r);
		tree *ret = comb(L_qr, R_qr);
		return ret;
	}
};

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

	tree *root = new tree(0, 1, n);
	root-> build(0);

	while(m--) {
		int l, r, k;
		cin >> l >> r >> k;
		tree *q = root-> query(l, r);
		cout << (q-> ans <= k) << '\n';
	}
	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