제출 #644026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
644026		ymm	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1034 ms	138440 KiB

sortbooks

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1'000'010;

int a[N], n;

int fen[N];
int get(int r)
{
	int ans = 0;
	while (r) {
		ans = max(ans, fen[r]);
		r -= r & -r;
	}
	return ans;
}
void up(int i, int x)
{
	++i;
	while (i <= n) {
		fen[i] = max(fen[i], x);
		i += i & -i;
	}
}

vector<int> A[N];
int ans[N];
vector<int> qry[N];
int r[N], k[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> n >> q;
	Loop (i,0,n)
		cin >> a[i];
	vector<int> st;
	Loop (i,0,n) {
		while (st.size() && a[st.back()] <= a[i])
			st.pop_back();
		if (st.size())
			A[st.back()].push_back(i);
		st.push_back(i);
	}
	Loop (i,0,q) {
		int l, r, k;
		cin >> l >> r >> k;
		qry[l-1].push_back(i);
		::k[i] = k;
		::r[i] = r;
	}
	LoopR (l,0,n) {
		for (int v : A[l])
			up(v, a[l] + a[v]);
		for (int i : qry[l])
			ans[i] = get(r[i]) <= k[i];
	}
	Loop (i,0,q) {
		cout << ans[i] << '\n';
	}
}

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