oj.uz

Submission #492412

# Submission time Handle Problem Language Result Execution time Memory
492412 2021-12-07T06:52:57 Z infertechno2 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 33104 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Size=1e6+1;

ll w[Size],min_tree[4*Size],max_tree[4*Size];

void update(ll l,ll r,ll i,bool min_or_max,ll val){
    if(l==r){
        if(min_or_max){
            min_tree[i]=val;
        }else{
            max_tree[i]=val;
        }
    }else{
        ll mid=(l+r)/2;
        update(l,mid,i*2,min_or_max,val);
        update(mid+1,r,i*2+1,min_or_max,val);
        min_or_max ? min_tree[i]=min(min_tree[i*2],min_tree[i*2+1]) : max_tree[i]=max(max_tree[i*2],max_tree[i*2+1]);
    }
}
ll query(ll l,ll r,ll i,ll tl,ll tr,bool min_or_max){
    if(l>tr or r<tl){
        return -1;
    }
    if(l==r){
        if(min_or_max){
            return min_tree[i];
        }else{
            return max_tree[i];
        }
    }else{
        ll mid=(l+r)/2;
        ll n1=query(l,mid,i*2,tl,min(tr,mid),min_or_max);
        ll n2=query(mid+1,r,i*2+1,max(tl,mid+1),tr,min_or_max);
        if(n1==-1)return n2;
        if(n2==-1)return n1;
        if(min_or_max){
            return min(n1,n2);
        }else{
            return max(n1,n2);
        }
    }
}



void solve(){
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>w[i];
        update(0,n-1,1,false,w[i]);
        update(0,n-1,1,true,w[i]);
    }
    while(m--){
        ll l,r,k;
        cin>>l>>r>>k;
        l--; r--;
        ll low=query(0,n-1,1,l,r,true),high=query(0,n-1,1,l,r,false);
        cout<<(low+high<=k)<<endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 2 ms 332 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 3060 ms 33104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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