제출 #1219205

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

sortbooks

#include<bits/stdc++.h>
using namespace std;
struct query { int l,r,k,pos; };
const int MAXN=1e6+69;
int A[MAXN],pref[MAXN],fl[MAXN],fr[MAXN];
bool ans[MAXN];
//vector<query> vc[MAXN];
//void dnc(int l,int r,vector<query> vq)
//{
//	if(l==r)
//	{
//		for(auto v:vq) ans[v.pos]=true;
//		return ;
//	}
//	int mid=(l+r)/2;
//	vector<query> va,vb;
//	for(auto v:vq) if(v.r<=mid) va.push_back(v);
//	else if(mid<v.l) vb.push_back(v);
//	else vc[v.r].push_back(v);
//	dnc(l,mid,va);
//	dnc(mid+1,r,vb);
//	pref[mid+1]=fl[mid+1]=fr[mid]=0;
//	set<int> st;
//	for(int i=mid;i>=l;i--)
//	{
//		auto res=st.lower_bound(A[i]);
//		if(res==st.begin()) fl[i]=fl[i+1];
//		else fl[i]=max(fl[i+1],(*prev(res))+A[i]);
//		pref[i]=max(pref[i+1],A[i]),st.insert(A[i]);
//	}
//	st.clear();
//	int mx=0;
//	for(int i=mid+1;i<=r;i++)
//	{
//		fr[i]=fr[i-1];
//		if(mx>A[i]) fr[i]=max(fr[i],mx+A[i]);
//		mx=max(mx,A[i]),st.insert(A[i]);
//		for(auto v:vc[i])
//		{
//			bool ck=(fl[v.l]<=v.k&&fr[v.r]<=v.k);
//			auto res=st.lower_bound(pref[v.l]);
//			if(res!=st.begin()&&pref[v.l]+(*prev(res))>v.k) ck=false;
//			ans[v.pos]=ck;
//		}
//		vc[i].clear();
//	}
//}
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];
    vector<query> vq;
    for(int i=1;i<=q;i++)
    {
		int l,r,k;
		cin>>l>>r>>k;
		int mx=0;
		for(int a=l;a<=r;a++) for(int b=a+1;b<=r;b++) if(A[a]>A[b]) mx=max(mx,A[a]+A[b]);
		if(mx<=k) cout<<"1\n";
		else cout<<"0\n";
//		vq.push_back({l,r,k,i});
	}
//	dnc(1,n,vq);
//	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

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