oj.uz

Submission #643437

# Submission time Handle Problem Language Result Execution time Memory
643437 2022-09-22T03:34:24 Z czhang2718 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2099 ms 158672 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

int n, q;
const int N=1e6;
int mx[4*N], lazy[4*N];
int a[N];

void push(int x, int lx, int rx){
    if(rx-lx==1 || !lazy[x]) return;
    for(int y:{2*x+1, 2*x+2}){
        mx[y]+=lazy[x];
        lazy[y]+=lazy[x];
    }
    lazy[x]=0;
}

void add(int l, int r, int v, int x, int lx, int rx){
    push(x,lx,rx);
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r){
        lazy[x]+=v;
        mx[x]+=v;
        return;
    }
    int m=(lx+rx)/2;
    add(l,r,v,2*x+1,lx,m);
    add(l,r,v,2*x+2,m,rx);
}

void add(int l, int r, int v){
    if(r<=l) return;
    add(l, r, v, 0, 0, n);
}

int get_mx(int l, int r, int x, int lx, int rx){
    push(x,lx,rx);
    if(lx>=r || rx<=l) return -1;
    if(lx>=l && rx<=r){
        return mx[x];
    }
    int m=(lx+rx)/2;
    return max(get_mx(l,r,2*x+1,lx,m), get_mx(l,r,2*x+2,m,rx));
}

int get_mx(int l, int r){
    return get_mx(l,r,0,0,n);
}

void build(int x, int lx, int rx){
    if(rx-lx==1){
        mx[x]=a[lx];
        return;
    }
    int m=(lx+rx)/2;
    build(2*x+1, lx, m);
    build(2*x+2, m, rx);
    mx[x]=max(mx[2*x+1], mx[2*x+2]);
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
                                                          
    cin >> n >> q;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    build(0, 0, n);
    vector<vector<int>> qu(n), lr(q, vector<int>(2));
    vector<int> ans(q), k(q);
    for(int i=0; i<q; i++){
        cin >> lr[i][0] >> lr[i][1] >> k[i];
        lr[i][0]--, lr[i][1]--;
        qu[lr[i][0]].push_back(i);
    }

    stack<int> s;
    s.push(n);
    int inf=2e9;
    for(int i=n-1; i>=0; i--){
        int lst=i;
        while(s.size()>1 && a[i]>a[s.top()]){
            int j=s.top(); s.pop();
            int j2=s.top();
            add(j+1, j2, -a[j]);
            add(j,j+1,-inf+a[j]);
        }
        add(i,i+1,-a[i]+inf);
        add(i+1,s.top(),a[i]);
        s.push(i);

        for(int p:qu[i]){
            ans[p]=get_mx(i,lr[p][1]+1);
        }
    }

    for(int i=0; i<q; i++){
        cout << (k[i]>=ans[i]) << "\n";
    }
}
// range add 
// range max
// tuck a knife with my heart up my sleeve

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:83:13: warning: unused variable 'lst' [-Wunused-variable]
   83 |         int lst=i;
      |             ^~~

Subtask #1
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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