Submission #643441

#	Time	Username	Problem	Language	Result	Execution time	Memory
643441		czhang2718	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2685 ms	164408 KiB

sortbooks

#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);
    mx[x]=max(mx[2*x+1], mx[2*x+2]);
}

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--){
        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);
        }
        add(i,i+1,-inf);
        add(i+1,s.top(),a[i]);
        s.push(i);
        // for(int j=0; j<n; j++){
        //     cout << get_mx(j,j+1) << " ";
        // }
        // cout << '\n';

        for(int p:qu[i]){
            // cout << "ans " << p << " " << get_mx(i,lr[p][1]+1) << "\n";
            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

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23