제출 #341193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341193		wwdd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1008 ms	119972 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
class ST {
	private:
		vl st;
		int n;
	public:
		ST(int n_) {
			n = n_;
			st.assign(2*n,0);
		}
		void up(ll l, ll r, ll val) {
			l += n;
			r += n;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {
					st[l] = max(st[l],val);
					l++;
				}
				if(r&1) {
					--r;
					st[r] = max(st[r],val);
				}
			}
		}
		ll get(int p) {
			p += n;
			ll res = 0;
			while(p > 0) {
				res = max(res,st[p]);
				p >>= 1;
			}
			return res;
		}
};
vl w;
struct Q {
	ll idx,lf,rt,lim;
	bool operator<(const Q& other) {
		return lf < other.lf;
	}
};
vector<vector<pl>> up;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n,q;
	cin >> n >> q;
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
	}
	up.assign(n,vector<pl>());
	stack<pl> su;
	for(int i=n-1;i>=0;i--) {
		while(!su.empty() && su.top().second < w[i]) {
			up[i].push_back(su.top());
			su.pop();
		}
		su.emplace(i,w[i]);
	}
	vector<Q> qv;
	for(int i=0;i<q;i++) {
		ll lf,rt,lim;
		cin >> lf >> rt >> lim;
		lf--;rt--;
		qv.push_back({i,lf,rt,lim});
	}
	sort(qv.begin(),qv.end());
	vl ans(q,0);
	int xv = n-1;
	ST st(n);
	for(int i=q-1;i>=0;i--) {
		while(xv >= qv[i].lf) {
			for(const auto& it: up[xv]) {
				st.up(it.first,n,it.second+w[xv]);
			}
			xv--;
		}
		ans[qv[i].idx] = qv[i].lim >= st.get(qv[i].rt);
	}
	for(int i=0;i<q;i++) {
		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