Submission #1291416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291416		haha	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	921 ms	50164 KiB

sortbooks

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=1e6+5;

int n,m;
int w[maxn],L[maxn],R[maxn],ans[maxn];
ll k[maxn],tree[4*maxn];
stack<int> st;
pair<int,int> p[maxn];

void update(int id,int l,int r,int pos,ll val)
{
    if(l>pos||pos>r) return;
    if(l==r){
        tree[id]=max(tree[id],val);
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,pos,val);
    update(id*2+1,mid+1,r,pos,val);
    tree[id]=max(tree[id*2],tree[id*2+1]);
}

ll get(int id,int l,int r,int u,int v)
{
    if(r<u||v<l) return 0;
    if(u<=l&&r<=v) return tree[id];
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++){
        cin>>L[i]>>R[i]>>k[i];
        p[i].f=R[i];
        p[i].s=i;
    }
    sort(p+1,p+m+1);
    int j=1;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&w[st.top()]<=w[i]) st.pop();
        if(!st.empty()){
            update(1,1,n,st.top(),1LL*w[i]+w[st.top()]);
        }
        while(j<=m&&p[j].f<=i){
            int id=p[j].s;
            if(get(1,1,n,L[id],R[id])>k[id]){
                ans[id]=1;
            }
            j++;
        }
        st.push(i);
    }
    for(int i=1;i<=m;i++) cout<<1-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