제출 #1219282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219282		boclobanchat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	490 ms	56528 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
struct query { int l,k,pos; };
const int MAXN=1e6+69;
vector<query> vq[MAXN];
int A[MAXN],nex[MAXN],fen[MAXN];
bool ans[MAXN];
stack<int> st;
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]=max(fen[i],val); }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans=max(ans,fen[i]);return ans; }
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<=q;i++)
    {
    	int l,r,k;
    	cin>>l>>r>>k;
    	vq[r].push_back({l,k,i});
	}
	for(int i=1;i<=n;i++)
	{
		while(!st.empty()&&A[i]>=A[st.top()]) st.pop();
    	if(!st.empty()) update(n-st.top()+1,n,A[st.top()]+A[i]);
    	st.push(i);
    	for(auto v:vq[i]) ans[v.pos]=(get(n-v.l+1)<=v.k);
	}
	for(int i=1;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