Submission #798250

#	Time	Username	Problem	Language	Result	Execution time	Memory
798250		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3058 ms	262144 KiB

sortbooks

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

struct node {
	int cnt;
	node *l, *r;
	node(): cnt(0), l(nullptr), r(nullptr) {}
	node(int cnt): cnt(cnt), l(nullptr), r(nullptr) {}
	node(node *l, node *r): cnt(0), l(l), r(r) {
		if (l) cnt += l->cnt;
		if (r) cnt += r->cnt;
	}
};

typedef node * pnode;

const int maxn = 1e6+3, maxm = 1e6+3, maxw = 1e9+3;
int n, m;
pair<int, int> w[maxn];
map<int, int> mp1;
int mp2[maxn];
pnode roots[maxn];
int mx[4*maxn], mxsum[4*maxn];

pnode build1(int l, int r) {
	if (l == r) return new node();
	int mid = (l+r)/2;
	return new node(build1(l, mid), build1(mid+1, r));
}

pnode update1(pnode p, int l, int r, int pos) {
	if (l == r) return new node(p->cnt + 1);
	int mid = (l+r)/2;
	if (pos <= mid) return new node(update1(p->l, l, mid, pos), p->r);
	return new node(p->l, update1(p->r, mid+1, r, pos));
}

int query1(pnode pl, pnode pr, int l, int r, int k) {
	if (l > k || pr->cnt - pl->cnt == 0) return -1;
	if (l == r) return l;
	int mid = (l+r)/2;
	if (r <= k) {
		if (pr->r->cnt - pl->r->cnt > 0) return query1(pl->r, pr->r, mid+1, r, k);
		if (pr->l->cnt - pl->l->cnt > 0) return query1(pl->l, pr->l, l, mid, k);
		return -1;
	}
	return max(query1(pl->l, pr->l, l, mid, k), query1(pl->r, pr->r, mid+1, r, k));
}

void build2(int l, int r, int v) {
	if (l == r) {
		mxsum[v] = -1;
		mx[v] = w[l].first;
	} else {
		int mid = (l+r)/2;
		build2(l, mid, v*2);
		build2(mid+1, r, v*2+1);
		int mxr = query1(roots[mid+1], roots[r+1], 0, mp1.size()-1, mp1[mx[v*2]]);
		mxsum[v] = max({mxsum[v*2], mxsum[v*2+1], (mxr == -1 ? -1 : mx[v*2] + mp2[mxr])});
		mx[v] = max(mx[v*2], mx[v*2+1]);
	}
}

pair<int, int> query(int l, int r, int v, int lb, int rb) {
	if (r < lb || l > rb) return make_pair(-1, -1);
	if (l >= lb && r <= rb) return make_pair(mx[v], mxsum[v]);
	
	int mid = (l+r)/2;
	auto resl = query(l, mid, v*2, lb, rb);
	auto resr = query(mid+1, r, v*2+1, lb, rb);

	int mxr = -1;
	if (resl.first != -1 && mid+1 <= rb) mxr = query1(roots[mid+1], roots[rb+1], 0, mp1.size()-1, mp1[resl.first]);

	return make_pair(max(resl.first, resr.first), max({
		resl.second,
		resr.second,
		(mxr == -1 ? -1 : resl.first + mp2[mxr])
	}));
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; i++) {
		cin >> w[i].first;
		w[i].second = i;
	}

	sort(w, w+n);
	for (int l=0, i=0; l<n; i++) {
		int r = l;
		while (r < n && w[l].first == w[r].first) r++;
		mp1[w[l].first] = i;
		mp2[i] = w[l].first;
		l = r;
	}
	sort(w, w+n, [](const pair<int, int> &pa, const pair<int, int> &pb) {
		return pa.second < pb.second;
	});


	roots[0] = build1(0, mp1.size()-1);
	for (int i=1; i<=n; i++) roots[i] = update1(roots[i-1], 0, mp1.size()-1, mp1[w[i-1].first]);
	build2(0, n-1, 1);

	for (int i=0; i<n; i++) {
		for (int j=i; j<n; j++) {
			cout << i << ' ' << j << ' ' << query(0, n-1, 1, i, j).second << '\n';
		}
	}

	while (m--) {
		int l, r, k;
		cin >> l >> r >> k;
		cout << (query(0, n-1, 1, l-1, r-1).second <= 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