제출 #1134913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134913		hamzabc	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3094 ms	8360 KiB

sortbooks

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


vector<long long int> lst, cvp;
long long int N, Q;


class segtree{
private:
	vector<long long int> tre;

	void _set(long long int ind, long long int x, long long int l, long long int r, long long int s){
		if (ind < l || r < ind)
			return;
		tre[s] = max(tre[s], x);
		if (l == r)
			return;
		long long int m = (l + r) >> 1;
		_set(ind, x, l, m, s << 1);
		_set(ind, x, m + 1, r, (s << 1) | 1);
	}
	
	long long int _get(long long int ind, long long int l, long long int r, long long int s){
		if (r < ind)
			return LONG_LONG_MIN;
		if (ind <= l)
			return tre[s];
		long long int m = (l + r) >> 1;
		return max(_get(ind, l, m, s << 1),	_get(ind, m + 1, r, (s << 1) | 1));
	}
public:
	segtree(){
		tre.resize(N * 8);
	}

	void set(long long int ind, long long int x){
		_set(ind, x, 0, N + 1, 1);
	}

	long long int get(long long int L){
		return _get(L, 0, N + 1, 1);
	}
};


void solve(){
	cin >> N >> Q;
	lst.resize(N);
	for (int i = 0; i < N; i++)
		cin >> lst[i];
	vector<array<long long int, 4>> q;
	q.reserve(Q);
	cvp.resize(Q, 1);
	for (int i = 0; i < Q; i++){
		long long int a, b, w;
		cin >> a >> b >> w;
		a--; b--;
		if (a != b)
			q.push_back({a, b, w, i});
	}
	
	sort(all(q), [](const array<long long int, 4> a, const array<long long int, 4> b) -> bool{ return a[1] < b[1]; });

	segtree tree = segtree();

	stack<pair<long long int, long long int>> stc;
	long long int r = 0;
	for (auto quest : q){
		while (r <= quest[1]){
			while (stc.size() && stc.top().first < lst[r]){
				stc.pop();
			}
			if (stc.size())
				tree.set(stc.top().second, stc.top().first + lst[r]);
			stc.push({ lst[r], r });
			r++;
		}
		cvp[quest[3]] = tree.get(quest[0]) <= quest[2];
	}

	for (int i = 0; i < Q; i++){
		cout << cvp[i] endl;
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long int M;
	cin >> N >> M;
	lst.resize(N);
	for (int i = 0; i < N; i++)
		cin >> lst[i];
	for (int o = 0; o < M; o++){
		long long int l, r, x, mx = -1, cost = 0;
		cin >> l >> r >> x;
		l--; r--;
		for (int i = l; i <= r; i++){
			if (lst[i] < mx){
				mx = lst[i];
			}else{
				cost = max(cost, mx + lst[i]);
			}
		}
		cout << (cost <= x) endl;
	}
	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