Submission #1155280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155280		imarn	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	3098 ms	171728 KiB

sortbooks

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=1e6+5;
int w[mxn];
int ans[mxn]{0};
int res[mxn]{0};
int hi[mxn];
vector<t3>t[4*mxn];
void push(int i,int l,int r,int tl,int tr,int id){
    if(r<tl||l>tr)return;
    int m=(l+r)>>1;
    if(tl>=l&&tr<=r&&tl<=m&&tr>m){t[i].pb({tr,tl,id});return;}
    push(2*i,l,m,tl,tr,id);push(2*i+1,m+1,r,tl,tr,id);
}
int pre[mxn]{0};
multiset<int>ml,mr;
void dac(int id,int l,int r){
    if(l>=r)return;
    int m=(l+r)>>1;
    hi[m]=w[m];
    for(int i=m-1;i>=l;i--)hi[i]=max(hi[i+1],w[i]);
    int mx=w[m+1];pre[m+1]=0;
    for(int i=m+2;i<=r;i++){
        if(w[i]<mx)pre[i]=max(pre[i-1],w[i]+mx);
        else pre[i]=pre[i-1];
        mx=max(mx,w[i]);
    }ml.insert(w[m]);pre[m]=0;
    for(int i=m-1;i>=l;i--){
        if(w[i]>*(ml.begin()))pre[i]=max(pre[i+1],w[i]+*(--ml.lower_bound(w[i])));
        else pre[i]=pre[i+1];
        ml.insert(w[i]);
    }
    sort(all(t[id]));int idx=m+1;
    for(auto [tr,tl,i] : t[id]){
        while(idx<=r&&idx<=tr)mr.insert(w[idx++]);
        ans[i]=max({pre[tl],pre[tr]});
        if(hi[tl]>*(mr.begin()))ans[i]=max(ans[i],hi[tl]+*(--mr.lower_bound(hi[tl])));
    }ml.clear();mr.clear();
    dac(2*id,l,m);dac(2*id+1,m+1,r);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=m;i++){
        int l,r,k;cin>>l>>r>>k;
        res[i]=k;
        if(l==r)ans[i]=0;
        else push(1,1,n,l,r,i);
    }
    dac(1,1,n);
    for(int i=1;i<=m;i++){
        cout<<(res[i]>=ans[i])<<'\n';

    }
}

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