Submission #711291

#	Time	Username	Problem	Language	Result	Execution time	Memory
711291		onlk97	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1564 ms	141560 KiB

sortbooks

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
int seg[4000040];
void update(int id,int tl,int tr,int pos,int val){
    if (tl==tr){
        seg[id]=max(seg[id],val);
        return;
    }
    int tm=(tl+tr)/2;
    if (pos<=tm) update(2*id,tl,tm,pos,val);
    else update(2*id+1,tm+1,tr,pos,val);
    seg[id]=max(seg[2*id],seg[2*id+1]);
}
int query(int id,int tl,int tr,int l,int r){
    if (l>r) return 0;
    if (l<=tl&&tr<=r) return seg[id];
    int tm=(tl+tr)/2;
    int lx=query(2*id,tl,tm,l,min(r,tm));
    int rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return max(lx,rx);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin>>n>>m;
    int w[n+1];
    for (int i=1; i<=n; i++) cin>>w[i];
    tii qu[m+1];
    vector <tii> hang[n+1];
    for (int i=1; i<=m; i++){
        cin>>qu[i].x.x>>qu[i].x.y>>qu[i].y;
        hang[qu[i].x.y].pb({{qu[i].x.x,qu[i].y},i});
    }
    bool ans[m+1];
    for (int i=1; i<=m; i++) ans[i]=1;
    stack <pii> st;
    for (int i=1; i<=n; i++){
        while (!st.empty()&&st.top().x<=w[i]) st.pop();
        if (!st.empty()) update(1,1,n,st.top().y,w[st.top().y]+w[i]);
        st.push({w[i],i});
        for (auto j:hang[i]){
            if (query(1,1,n,j.x.x,i)>j.x.y) ans[j.y]=0;
        }
    }
    for (int i=1; i<=m; 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