oj.uz

Submission #667623

# Submission time Handle Problem Language Result Execution time Memory
667623 2022-12-01T20:02:30 Z White Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1142 ms 100176 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

long long treeMin[4000005],red[1000005],MIN,nex[1000005];
pair<long long,long long>treeMax[4000005],MAX;

void build_tree(long long l,long long r,long long now){
    if(l==r){
        treeMax[now]=make_pair(red[l],l);
        treeMin[now]=red[l];
        return ;
    }

    long long mid=(l+r)/2;
    build_tree(l,mid,now*2+1);
    build_tree(mid+1,r,now*2+2);
    treeMax[now]=max(treeMax[now*2+1],treeMax[now*2+2]);
    treeMin[now]=min(treeMin[now*2+1],treeMin[now*2+2]);
    //cout<<treeMax[now]<<"-"<<treeMin[now]<<endl;
    return ;
}

void find_tree(long long l,long long r,long long L,long long R,long long now){
    if(l>=L && r<=R){
            //cout<<treeMax[now]<<l<<" "<<r<<endl;
        MAX=max(MAX,treeMax[now]);
        MIN=min(MIN,treeMin[now]);
        return ;
    }

    if(r<L || l>R){
        return ;
    }

    long long mid=(l+r)/2;
    find_tree(l,mid,L,R,now*2+1);
    find_tree(mid+1,r,L,R,now*2+2);
}

int main ()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,m,bob;
    cin>>n>>m;
    for(long long i=0;i<n;i++)cin>>red[i];
    nex[0]=0;
    for(long long i=1;i<=n;i++){
        if(red[i]>=red[i-1])nex[i]=nex[i-1];
        else nex[i]=i;
    }
    build_tree(0,n-1,0);

    for(long long i=0;i<m;i++){
        long long l,r,k;
        cin>>l>>r>>k;
        l--;r--;
        MIN=10000000;
        MAX=make_pair(-1,0);
        find_tree(0,n-1,l,r,0);

        if(MAX.second!=r){
            if(MAX.first+MIN<=k)cout<<1<<endl;
            else cout<<0<<endl;
        }else{
            bob=MIN;
            r=nex[MAX.second]-1;
            if(r<=l)cout<<1<<endl;
            else{
                find_tree(0,n-1,l,r,0);
                if(MAX.first+bob<=k)cout<<1<<endl;
                else cout<<0<<endl;
            }
        }
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 67160 KB Output is correct
2 Incorrect 1142 ms 100176 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -