oj.uz

Submission #952765

# Submission time Handle Problem Language Result Execution time Memory
952765 2024-03-24T18:25:53 Z idiotcomputer Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++11
0 / 100
 3000 ms 59900 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e6;
int n;
int vals[mxN];

int smin[4*mxN+1];
int smax[4*mxN+1];
int miss[4*mxN+1];

void build(int l = 0, int r = n-1, int idx = 0){
    if (l == r){
        smin[idx] = vals[l];
        smax[idx] = vals[l];
        miss[idx] = -1;
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
    smin[idx] = min(smin[2*idx+1],smin[2*idx+2]);
    smax[idx] = max(smax[2*idx+1],smax[2*idx+2]);
    if (miss[2*idx+2] != -1){
        miss[idx] = max(smax[2*idx+1],miss[2*idx+2]);
    } else {
        if (smax[2*idx+1] <= smin[2*idx+2]){
            miss[idx] = miss[2*idx+1];
        } else {
            miss[idx] = smax[2*idx+1];
        }
    }
    return;
}

int qmin(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
    if (tl > tr) return 2e9;
    if (l > tr || r < tl){
        return 2e9;
    } 
    if (l >= tl && r <= tr){
        return smin[idx];
    }
    int m = (l+r)/2;
    return min(qmin(tl,tr,l,m,2*idx+1), qmin(tl,tr,m+1,r,2*idx+2));
}

int qmax(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
    if (tl > tr) return 0;
    if (l > tr || r < tl){
        return 0;
    } 
    if (l >= tl && r <= tr){
        return smax[idx];
    }
    int m = (l+r)/2;
    return max(qmax(tl,tr,l,m,2*idx+1), qmax(tl,tr,m+1,r,2*idx+2));
}

int query(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl){
        return -1;
    } 
    if (l >= tl && r <= tr){
        return miss[idx];
    }
    int m = (l+r)/2;
    int v1 = query(tl,tr,l,m,2*idx+1);
    int v2 = query(tl,tr,m+1,r,2*idx+2);
    int cmax = qmax(max(tl,l),min(tr,m),l,m,2*idx+1);
    int cmin = qmin(max(tl,m+1),min(tr,r),m+1,r,2*idx+2);
    if (v2 != -1) return max(cmax,v2);
    if (cmax <= cmin) return v1;
    return cmax;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m;
    cin >> n >> m;
    
    for (int i =0; i < n; i++) cin >> vals[i];
    
    build();
    int l,r,k;
    for (int i = 0; i < m; i++){
        cin >> l >> r >> k;
        l -= 1;
        r -= 1;
        int v = query(l,r);
        int cmin = qmin(l,r);
        if (v == -1 || cmin + v <= k) cout << "1\n";
        else cout << "0\n";
    }
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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