Submission #954261

#	Time	Username	Problem	Language	Result	Execution time	Memory
954261		starchan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	943 ms	122264 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
struct segment_tree//we need a seg tree for max
{
	vector<int> tree;
	void init(int n)
	{
		tree.resize(4*n+69, 0);
		return;
	}
	void upd(int pos, int val, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = max(tree[id], val);
			return;
		}
		int m = (l+r)/2;
		if(pos <= m)
			upd(pos, val, 2*id, l, m);
		else
			upd(pos, val, 2*id+1, m+1, r);
		tree[id] = max(tree[2*id], tree[2*id+1]);
		return;
	}
	int query(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return 0;
		if(ql <= l && r <= qr)
			return tree[id];
		int m = (l+r)/2;
		int s1 = query(ql, qr, 2*id, l, m);
		int s2 = query(ql, qr, 2*id+1, m+1, r);
		return max(s1, s2);
	}
};
signed main()
{
	fast();
	segment_tree work;
	int n, m;
	cin >> n >> m;
	work.init(n);
	vector<pair<in, in>> vv(m);
	vector<int> w(n+1);
	vector<int> pr(n+1);
	for(int i = 1; i <= n; i++)
	{
		pr[i] = i-1;
		cin >> w[i];
	}
	w[0] = INF;
	for(int i = 1; i <= n; i++)
	{
		while(w[pr[i]] <= w[i])
			pr[i] = pr[pr[i]];
	}
	for(int i = 0; i < m; i++)
	{
		int l, r, k;
		cin >> l >> r >> k;
		vv[i] = {{r, l}, {k, i}};
	}
	int ans[m];
	sort(vv.begin(), vv.end());
	int up = 0;
	for(auto Q: vv)
	{
		int l, r, k, i; l = Q.f.s; r = Q.f.f; k = Q.s.f, i = Q.s.s;
		while(up < r)
		{
			up++;
			work.upd(pr[up], w[up]+w[pr[up]], 1, 0, n);
		}
		int ANS = work.query(l, r, 1, 0, n);
		ans[i] = (ANS<=k);
	}
	for(int i = 0; i < m; i++)
		cout << ans[i] << "\n";
	return 0;
}	

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