Submission #343948

#	Time	Username	Problem	Language	Result	Execution time	Memory
343948		fixikmila	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1804 ms	102956 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
struct cat{ll a,b,c;};
vector<cat>b[1000000];
ll a[1000000],c[1000000];
ll tree[4000001];
void update(ll l,ll x,ll v,ll tl,ll tr){
    if(tl==l&&tr==tl)tree[v]=max(tree[v],x);
    else if(tl>l||tr<l){
        return;
    }
    else{
        ll tm=(tl+tr)/2;
        update(l,x,2*v,tl,tm),update(l,x,2*v+1,tm+1,tr);
        tree[v]=max(tree[2*v+1],tree[2*v]);
    }
}
ll get_max(ll l,ll r,ll v,ll tl,ll tr){
    if(tl>=l&&tr<=r)return tree[v];
    else if(tl>r||tr<l)return LLONG_MIN;
    else{
        ll tm=(tl+tr)/2;
        return max(get_max(l,r,2*v,tl,tm),get_max(l,r,2*v+1,tm+1,tr));
    }
}
int main()
{
    //freopen("stones.in","r",stdin);
    //freopen("stones.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++){
        cin>>l>>r>>k;
        l--,r--;
        cat f;
        f.a=l,f.b=k,f.c=i;
        b[r].push_back(f);
    }
    stack<ll>s;
    for(int i=0;i<n;i++){
        while(s.size()&&a[s.top()]<=a[i])s.pop();
        if(s.size()){
            ll j=s.top();
            update(j,a[i]+a[j],1,0,n-1);
        }
        s.push(i);
        for(auto u : b[i]){
            l=u.a,k=u.b;
            ll nom=u.c;
            c[nom]=get_max(l,n-1,1,0,n-1)<=k?1:0;
        }
    }
    for(int i=0;i<m;i++)cout<<c[i]<<"\n";
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:44:8: warning: unused variable 't' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |        ^
sortbooks.cpp:44:20: warning: unused variable 'sum' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                    ^~~
sortbooks.cpp:44:34: warning: unused variable 'x' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                  ^
sortbooks.cpp:44:38: warning: unused variable 'y' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                      ^
sortbooks.cpp:44:42: warning: unused variable 'z' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                          ^
sortbooks.cpp:44:46: warning: unused variable 'ans' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                              ^~~
sortbooks.cpp:44:52: warning: unused variable 'mn' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                    ^~
sortbooks.cpp:44:65: warning: unused variable 'mx' [-Wunused-variable]
   44 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                                 ^~

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