Submission #1292172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292172		rayan_bd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	3100 ms	133532 KiB

sortbooks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int mxN = 1e6 + 100;

#define int long long

const int inf = 2e18 + 100;

int ar[mxN];

struct Node{
	int mn, mx, best, ex;
	Node(){
		mn = inf, mx = -inf, best = 0, ex = 0;
	}
	Node(int x){
		mn = x, mx = x, best = 0, ex = 1;
	}
} seg[mxN * 4];


Node merge(Node left, Node right){

	if(!left.ex) return right;
	if(!right.ex) return left;

	Node cur;

	cur.mn = min(left.mn, right.mn);

	cur.mx = max(left.mx, right.mx);

	cur.best = max(left.best, right.best);

	if(left.mx > right.mn) cur.best = max(cur.best, left.mx + right.mn);
	if(left.mx > right.mx) cur.best = max(cur.best, left.mx + right.mx);

	cur.ex = 1;

	return cur;
}

void build(int node, int start, int end){
	if(start == end){
		seg[node] = Node(ar[start]);
		return;
	}
	int mid = start + (end - start) / 2;
	build(node * 2 + 1, start, mid);
	build(node * 2 + 2, mid + 1, end);
	seg[node] = merge(seg[node * 2 + 1], seg[node * 2 + 2]);
}

Node query(int node, int start, int end, int l, int r){
	if(start > r || end < l) return Node();
	if(start >= l && end <= r) return seg[node];
	int mid = start + (end - start) / 2;
	return merge(query(node * 2 + 1, start, mid, l, r), query(node * 2 + 2, mid + 1, end, l, r));
}

signed main(){

	
	
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, q;
	cin >> n >> q;

	for(int i = 1; i <= n; ++i) cin >> ar[i];

	build(0, 1, n);

	while(q--){
		int l, r, k;
		cin >> l >> r >> k;
		int mx = 0, mx2 = 0;
		for(int i = l; i <= r; ++i){
			if(ar[i] < mx2){
				mx = max(mx, ar[i] + mx2);
			}
			mx2 = max(mx2, ar[i]);
		}
		if(mx > k) cout << "0\n";
		else cout << "1\n";
	}

	return 0;
}

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