oj.uz

Submission #154091

# Submission time Handle Problem Language Result Execution time Memory
154091 2019-09-18T11:01:49 Z beso123 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 3000 ms 61232 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 61232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 562 ms 8952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -