제출 #651302

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

sortbooks

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct BIT{
	int n;
	vector<int> bt;
	void init(int x){
		n=x;
		bt.resize(n+1);
	}
	void update(int x,int y){
		x++;
		for(;x>0;x-=(x&-x)){
			bt[x]=max(bt[x],y);
		}
	}
	int query(int x){
		x++;
		int ans=0;
		for(;x<=n;x+=(x&-x)){
			ans=max(ans,bt[x]);
		}
		return ans;
	}
}bt;
struct QU{
	int l,r,k;
	int id;
};
bool cmp(QU a,QU b){
	return a.r<b.r;
}
int main(){
    AquA;
	int n,m;
	cin >> n >> m;
	bt.init(n);
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	vector<QU> vq(m);
	vector<int> ans(m);
	for(int i=0;i<m;i++){
		cin >> vq[i].l >> vq[i].r >> vq[i].k;
		vq[i].l--;
		vq[i].r--;
		vq[i].id=i;
	}
	sort(vq.begin(),vq.end(),cmp);
	int r=0;
	vector<int> s;
	for(int i=0;i<n;i++){
		while(s.size() && v[s.back()]<=v[i]){
			s.pop_back();
		}
		if(s.size()){
			bt.update(s.back(),v[s.back()]+v[i]);
		}
		s.push_back(i);
		while(r<m && vq[r].r==i){
			if(bt.query(vq[r].l)<=vq[r].k){
				ans[vq[r].id]=1;
			}
			r++;
		}
	}
	for(int i=0;i<m;i++){
		cout << ans[i] << "\n";
	}
    return 0;
}

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