Submission #503828

#	Time	Username	Problem	Language	Result	Execution time	Memory
503828		DragonO_o	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	154 ms	111584 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define all(a) a.begin(),a.end()
#define int long long

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef vector<ll>vll;
typedef vector<int>vi;
typedef vector<bool>vb;
typedef vector<vi>vvi;
typedef vector<vll>vvll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;

const int N=1e6+99;

int w[N],k[N],a[N],t[N*4],ans[N];
vi cur[N];
vpii v[N];

void build(int v,int l,int r){
    if(l==r){
        t[v]=a[l];
        return;
    }
    int V=v<<1LL,mid=l+r>>1LL;
    build(V,l,mid);
    build(V+1,mid+1,r);
    t[v]=max(t[V],t[V+1]);
}

void upd(int v,int l,int r,int pos,int val){
     if(l==r){
        t[v]=val;
        return;
     }
     int V=v<<1LL,mid=l+r>>1LL;
     if(pos<=mid){
        upd(V,l,mid,pos,val);
     }
     else{
        upd(V+1,mid+1,r,pos,val);
     }
     t[v]=max(t[V],t[V+1]);
}

int get(int v,int l,int r,int L,int R){
    if(l==L&&r==R){
        return t[v];
    }
    int V=v<<1LL,mid=l+r>>1LL;
    if(R<=mid){
        return get(V,l,mid,L,R);
    }
    if(L>mid){
        return get(V+1,mid+1,r,L,R);
    }
    return max(get(V,l,mid,L,mid),get(V+1,mid+1,r,mid+1,R));
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>w[i];
    }
    vpii st;
    st.pb({w[1],1});
    a[1]=-1;
    for(int i=2;i<=n;++i){
        while(st.back().x<=w[i]){
            st.pop_back();
        }
        if(!st.size()){
            a[i]=-1;
        }
        else{
            a[i]=st.back().x+w[i];
            cur[st.back().y].pb(i);
        }
        st.pb({w[i],i});
    }
    build(1,1,n);
    for(int i=1;i<=m;++i){
        int l,r;
        cin>>l>>r>>k[i];
        v[l].pb({r,i});
    }
    for(int l=1;l<=N-99;++l){
        if(!v[l].size()){
            continue;
        }
        for(auto [r,i]:v[l]){
            if(get(1,1,n,l,r)<=k[i]){
                ans[i]=1;
            }
        }
        for(auto pos:cur[l]){
            upd(1,1,n,pos,-1);
        }
    }
    for(int i=1;i<=m;++i){
        cout<<ans[i]<<"\n";
    }
}
/**
5 1
11 7 9 10 3
1 5 20
**/

Compilation message (stderr)

sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int V=v<<1LL,mid=l+r>>1LL;
      |                      ~^~
sortbooks.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:46:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |      int V=v<<1LL,mid=l+r>>1LL;
      |                       ~^~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:60:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int V=v<<1LL,mid=l+r>>1LL;
      |                      ~^~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |         for(auto [r,i]:v[l]){
      |                  ^

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