Submission #254826

#	Time	Username	Problem	Language	Result	Execution time	Memory
254826		vuhoanggiap	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3105 ms	105796 KiB

sortbooks

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef pair<int, int> ii;

void Fastio() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

int n, m; 
int a[1000005], pre[1000005]; 
bool Ans[1000005];
vector<int> pos[1000005];
vector<pair<ii, int> > Queries[1000005]; 

int ST[1000005 * 4]; 

void Upd(int i, int l, int r, int id, int val) {
	if(id < l or r < id) return; 
	if(l == r) {
		ST[i] = val; 
		return; 
	}
	int mid = (l + r) >> 1; 
	Upd(i << 1, l, mid, id, val);
	Upd(i << 1 | 1, mid + 1, r, id, val); 
	ST[i] = max(ST[i << 1], ST[i << 1 | 1]); 
}

int Query(int i, int l, int r, int L, int R) {
	if(R < l or r < L or L > R) return 0; 
	if(L <= l and r <= R) {
		return ST[i]; 
	}
	int mid = (l + r) >> 1; 
	return max(Query(i << 1, l, mid, L, R), Query(i << 1 | 1, mid + 1, r, L, R)); 
}

signed main()
{
	cin >> n >> m; 
	for(int i = 1; i <= n; i++) {
		cin >> a[i]; 
	}
	for(int i = 1; i <= m; i++) {
		int l, r, k; 
		cin >> l >> r >> k; 
		Queries[l].pb({{r, k}, i}); 
	}
	stack<int> S; 
	for(int i = 1; i <= n; i++) {
		while(!S.empty() and a[S.top()] < a[i]) S.pop(); 
		if(!S.empty()) {
			pre[i] = S.top(); 
		}
		S.push(i); 
	}
	for(int i = 1; i <= n; i++) {
		pos[pre[i]].pb(i); 
	}
	for(int i = 1; i <= n; i++) {
		Upd(1, 1, n, i, a[i] + a[pre[i]]); 
	}
	for(int l = 0; l <= n; l++) {
		for(auto T : Queries[l]) {
			int r = T.fi.fi, k = T.fi.se, id = T.se; 
			Ans[id] = (Query(1, 1, n, l, r) <= k); 
		}
		for(auto i : pos[l]) {
			Upd(1, 1, n, i, 0); 
		}
	}
	for(int i = 1; i <= m; i++) {
		cout << Ans[i] << '\n'; 
 	}
}

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