Submission #1171736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171736		coolboy19521	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	404 ms	242864 KiB

sortbooks

#include "bits/stdc++.h"

#define mxS 20000007
#define mxN 1000006

using namespace std;

struct stree{
	int ar[mxS], le[mxS], ri[mxS];
	
	void copy(int i, int j){
		ar[i] = ar[j], le[i] = le[j], ri[i] = ri[j];
	}
	
	void upd(int i, int x, int l, int r, int& v, int k){
		if (l < r){
			int mi = (l + r) / 2;
			int ro = v;
			
			if (i <= mi){
				ri[ro] = ri[k], le[ro] = ++ v;
				upd(i, x, l, mi, v, le[k]);
			} else {
				le[ro] = le[k], ri[ro] = ++ v;
				upd(i, x, mi + 1, r, v, ri[k]);
			}
			
			ar[ro] = max(ar[le[ro]], ar[ri[ro]]);
		} else
			ar[v] = max(x, ar[k]);
	}
	
	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 ans = INT_MIN;
			
			if (le[v]) ans = max(ans, qry(a, b, l, mi, le[v]));
			if (ri[v]) ans = max(ans, qry(a, b, mi + 1, r, ri[v]));
			
			return ans;
		} else
			return INT_MIN;
	}
} st;

int roots[mxN];
int w[mxN];

int main(){
	int N, M;
	cin >> N >> M;
	
	for (int i = 1; i <= N; i ++)
		cin >> w[i];
		
	stack<int> stk;
	int pr = 1;
	
	for (int i = 1; i <= N; i ++){
		while (stk.size() && w[i] > w[stk.top()]){
			stk.pop();
		}
		
		if (stk.size()){
			int v = stk.top(), s = w[v];
			roots[i] = pr;

			st.upd(v, w[v] + w[i], 1, mxN, pr, roots[i - 1]);
		} else {
			roots[i] = pr;
			st.copy(roots[i], roots[i - 1]);
		}
		
		stk.push(i);
		pr ++;
	}
	
	while (M --){
		int L, R, K;
		cin >> L >> R >> K;
		
		int loc = st.qry(L, R, 1, mxN, roots[R]);
		
		loc <= K ? puts("1") : puts("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