Submission #1171785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171785		coolboy19521	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1827 ms	34324 KiB

sortbooks

#include "bits/stdc++.h"

#define mxN 1000006

using namespace std;

struct stree{
	int ar[4 * mxN];
	
	void upd(int i, int x, int l, int r, int v){
		if (l < r){
			int mi = (l + r) / 2;
			
			if (i <= mi)
				upd(i, x, l, mi, v * 2);
			else
				upd(i, x, mi + 1, r, v * 2 + 1);
			
			ar[v] = max(ar[v * 2], ar[v * 2 + 1]);
		} else ar[v] = x;
	}
	
	int qry(int a, int b, int l, int r, int v){
		if (a <= l && r <= b)
			return ar[v];
		else if (a <= r && l <= b){
			int mi = (l + r) / 2;
			
			int lr = qry(a, b, l, mi, v * 2);
			int rr = qry(a, b, mi + 1, r, v * 2 + 1);
			
			return max(lr, rr);
		} else return INT_MIN;
	}
} st;

int ans[mxN];
int w[mxN];

int main(){
	int N, M;
	cin >> N >> M;
	
	for (int i = 1; i <= N; i ++)
		cin >> w[i];

	vector<tuple<int,int,int,int>> qrys;
	
	for (int i = 1; i <= M; i ++){
		int L, R, K;
		cin >> L >> R >> K;
		
		qrys.emplace_back(R, L, K, i);
	}
	
	sort(begin(qrys), end(qrys));
	
	stack<int> stk;
	int ls = 0;
	
	for (int i = 0; i < M; i ++){
		auto& [R, L, K, I] = qrys[i];
		
		if (ls < R){
			for (int j = ls + 1; j <= R; j ++){
				while (stk.size() && w[stk.top()] <= w[j]){
					stk.pop();
				}
			
				if (stk.size()){
					int v = stk.top();
					st.upd(v, w[v] + w[j], 1, N, 1);
				}
			
				stk.push(j);
			}
			
			ls = R;
		}
		
		int loc = st.qry(L, R, 1, N, 1);

		ans[I] = loc <= K;
	}
	
	for (int i = 1; i <= M; i ++)
		cout << ans[i] << endl;
}

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