제출 #1292130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292130		rayan_bd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1057 ms	135396 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);

	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;
		Node answer = query(0, 1, n, l, r);
		if(answer.best <= k) cout << "1\n";
		else cout << "0\n";
	}

	return 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