Submission #333670

#	Time	Username	Problem	Language	Result	Execution time	Memory
333670		vipghn2003	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1555 ms	22892 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;
int n,m,a[N];

struct node
{
    int mx,val;
}ST[4*N];

node mer(node a,node b)
{
    node res;
    res.mx=max(a.mx,b.mx);
    res.val=max(a.val,b.val);
    if(a.mx>b.mx) res.val=max(res.val,b.mx+a.mx);
    return res;
}

void build(int id,int l,int r)
{
    if(l==r)
    {
        ST[id].mx=a[l];
        ST[id].val=0;
        return ;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    ST[id]=mer(ST[id*2],ST[id*2+1]);
}

node get(int id,int l,int r,int u,int v)
{
    if(l>v||r<u) return {0,0};
    //cout<<l<<' '<<r<<' '<<ST[id].mx<<' '<<ST[id].val<<'\n';
    if(u<=l&&r<=v) return ST[id];
    int mid=(l+r)/2;
    return mer(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        node cur=get(1,1,n,l,r);
        if(cur.val>k) cout<<0;
        else cout<<1;
        cout<<'\n';
    }
}

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