Submission #1126763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126763		koukirocks	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	17 / 100	3095 ms	33644 KiB

sortbooks

#include<bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0);cin.tie(0)
#define F first
#define S second

using namespace std;
template<typename T>
using vvector = vector<vector<T>>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=0x3f3f3f3f;

pair<bool,pii> get(int l,int r,vvector<pair<bool,pii>> spt) {
    pair<bool,pii> ans={1,{INF,0}};
    for (int k=20;k>=0;k--) {
        // cout<<l<<" "<<r<<" lr\n"<<flush;
        if (l+(1<<k)-1<=r) {
            ans.F=ans.F and spt[l][k].F and ans.S.S<=spt[l][k].S.F;
            ans.S={min(ans.S.F,spt[l][k].S.F),max(ans.S.S,spt[l][k].S.S)};
            l+=(1<<k);
        }
    }
    return ans;
}

int main() {
    speed;
    int n,m;
    cin>>n>>m;
    vector<int> w(n+1);
    for (int i=1;i<=n;i++) {
        cin>>w[i];
    }
    while (m--) {
        int l,r,k;
        cin>>l>>r>>k;
        int mx=0;
        set<int> now;
        for (int i=r;i>=l;i--) {
            auto it=now.lower_bound(w[i]);
            if (it!=now.begin()) mx=max(mx,*prev(it)+w[i]);
            now.insert(w[i]);
        }
        if (mx<=k) cout<<"1\n";
        else cout<<"0\n";
    }
    return 0;
}

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