Submission #343314

#	Time	Username	Problem	Language	Result	Execution time	Memory
343314		fixikmila	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	123 ms	16516 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;};
cat tree[20001];
ll a[1000000];
void build_tree(ll v,ll tl,ll tr){
    if(tl==tr)tree[v].a=tl,tree[v].b=a[tl];
    else{
        ll tm=(tl+tr)/2;
        build_tree(2*v,tl,tm),build_tree(2*v+1,tm+1,tr);
        if(tree[2*v].b>tree[2*v+1].b)tree[v].a=tree[2*v].a,tree[v].b=tree[2*v].b;
        else tree[v].a=tree[2*v+1].a,tree[v].b=tree[2*v+1].b;
    }
}
cat 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<r){
        cat f;
        f.b=LLONG_MIN;
        return f;
    }
    ll tm=(tl+tr)/2;
    cat f=get_max(l,r,2*v,tl,tm),f1=get_max(l,r,2*v+1,tm+1,tr),f2;
    if(f.b>f1.b)f2.a=f.a,f2.b=f.b;
        else f2.a=f1.a,f2.b=f1.b;
        return f2;
}
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;
    vector<vector<ll>>c(1000);
    for(int i=0;i<n;i++)cin>>a[i],mx=max(mx,a[i]),mn=min(mn,a[i]);
    //c[a[i]].push_back(i);
    build_tree(1,0,n-1);
    for(int i=0;i<m;i++){
        cin>>l>>r>>k;
        l--,r--;
        z=1;
        if(max(n,m)<=5e3){
                ll mx1=-1;
                y=-1;
                for(int j=l;j<=r;j++){
                    if(y>a[j]){
                        mx1=max(mx1,a[j]+y);
                    }
                    y=max(y,a[j]);
                }
        if(mx1<=k)z=1;
            else z=0;
        }
        else if(mn>k){
            while(true){
                    if(r<l)break;
                cat f=get_max(l,r,1,0,n-1);
                if(f.a!=r){
                    z=0;
                    break;
                }
                r--;
            }
        }
        else if(mx<=1e3){
                y=-1;
                ll mx1=-1,v;
            for(int j=1;j<=1000;j++){
                if(c[j].size()==0)continue;
                if(c[j][0]>r||c[j].back()<l)continue;
                x=upper_bound(c[j].begin(),c[j].end(),r)-c[j].begin()-1;
                t=c[j][x];
                if(t<y){
                    mx1=max(mx1,j+v);
                }
                //cout<<t<<" "<<y<<endl;
                y=t;
                v=j;
            }
            if(mx1<=k)z=1;
            else z=0;
        }
        cout<<z;
        cout<<"\n";
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:46:20: warning: unused variable 'sum' [-Wunused-variable]
   46 |     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:46:46: warning: unused variable 'ans' [-Wunused-variable]
   46 |     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:88:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |                     mx1=max(mx1,j+v);
      |                                 ~^~

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