Submission #154091

#	Time	Username	Problem	Language	Result	Execution time	Memory
154091		beso123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3083 ms	61232 KiB

sortbooks

#include<bits/stdc++.h>
#define int long long
#define y second.first
#define x first
#define z second.second
#define pii pair<int,pair<int,int>>
using namespace std;
int n,m,a[1000005];
pii t[4000005];
void build(int v,int i,int j){
    if(i==j){
       t[v]={a[i],{a[i],0}};
       return;
    }
    int mid=(i+j)/2;
    build(v*2,i,mid);
    build(v*2+1,mid+1,j);
    if(t[v*2].y>t[v*2+1].x || t[v*2].y>t[v*2+1].y){
        t[v].z=max(t[v].z,t[v*2].y);
    }
    t[v].x=min(t[v*2].x,t[v*2+1].x);
    t[v].y=max(t[v*2].y,t[v*2+1].y);
}
int ans=-1;
pii get(int v,int i,int j,int l,int r){
    if(l>r)
    return {-1,{-1,0}};
    if(i==l && j==r){
        if(t[v].z!=0){
            ans=max(ans,t[v].z);
        }
        return t[v];
    }
    int mid=(i+j)/2;
    pii g1=get(v*2,i,mid,l,min(r,mid));
    pii g2=get(v*2+1,mid+1,j,max(mid+1,l),r);
    if(g1.x!=-1 && g2.x!=-1){
    if(g1.y>g2.x || g1.y>g2.y){
        ans=max(g1.y,ans);
    }
    pii p;
    p.x=min(g1.x,g2.x);
    p.y=max(g1.y,g2.y);
    return p;
    }
    if(g1.x!=-1)
        return g1;
    if(g2.x!=-1)
        return g2;

}
main(){
cin>>n>>m;
for(int k=1;k<=n;k++){
   cin>>a[k];
}
build(1,1,n);
for(int k=1;k<=m;k++){
   int l,r,s;
   cin>>l>>r>>s;
ans=-1;
pii g=get(1,1,n,l,r);
if(ans==-1){
       cout<<1<<endl;
}
else{
if(ans+g.x<=s)
    cout<<1<<endl;
else cout<<0<<endl;
}
}
return 0;
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3
*/

Compilation message (stderr)

sortbooks.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sortbooks.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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