Submission #1126762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126762		koukirocks	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3096 ms	327680 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;
    vvector<pair<bool,pii>> spt(n+1,vector<pair<bool,pii>>(21));
    for (int i=1;i<=n;i++) {
        cin>>spt[i][0].S.F;
        spt[i][0].S.S=spt[i][0].S.F;
        spt[i][0].F=true;
    }
    for (int k=1;k<=20;k++) {
        for (int i=1;i<=n-(1<<k)+1;i++) {
            spt[i][k].F=spt[i][k-1].F and spt[i+(1<<k-1)][k-1].F and spt[i][k-1].S.S<=spt[i+(1<<k-1)][k-1].S.F;
            spt[i][k].S.F=min(spt[i][k-1].S.F,spt[i+(1<<k-1)][k-1].S.F);
            spt[i][k].S.S=max(spt[i][k-1].S.S,spt[i+(1<<k-1)][k-1].S.S);
        }
    }
    while (m--) {
        int a,b,k;
        cin>>a>>b>>k;
        int l=a,r=b+1;
        while (l<r) {
            int mid=l+r>>1;
            auto s1=get(a,mid-1,spt);
            auto s2=get(mid,b,spt);
            if (s2.F and s1.S.S<=s2.S.F) r=mid;
            else l=mid+1;
        }
        auto s1=get(a,l-1,spt);
        auto s2=get(a,b,spt);
        // cout<<l<<" l\n";
        if (l==a or s1.S.S+s2.S.F<=k) cout<<"1\n";
        else cout<<"0\n";
    }
    return 0;
}

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