Submission #1161146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161146		AlgorithmWarrior	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	66 ms	3088 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int const INF=1e9+5;
int v[MAX];
int n,q;
struct query{
    int l,r,id;
    bool operator<(query ot){
        return l>ot.l;
    }
}qry[MAX];
int chef[MAX];

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

struct AIB{
    int v[MAX];
    int ub(int x){
        return x&(-x);
    }
    void add_val(int pos,int val){
        while(pos<=n){
            maxself(v[pos],val);
            pos+=ub(pos);
        }
    }
    int pref_max(int pos){
        int maxim=0;
        while(pos){
            maxself(maxim,v[pos]);
            pos-=ub(pos);
        }
        return maxim;
    }
}aib;

void read(){
    cin>>n>>q;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    for(i=1;i<=q;++i){
        cin>>qry[i].l>>qry[i].r;
        qry[i].id=i;
        cin>>chef[i];
    }
}

void rev_array(int v[]){
    int st=1,dr=n;
    while(st<dr){
        swap(v[st],v[dr]);
        ++st;
        --dr;
    }
}

void rev_problem(){
    rev_array(v);
    int i;
    for(i=1;i<=q;++i){
        qry[i].l=n-qry[i].l+1;
        qry[i].r=n-qry[i].r+1;
        swap(qry[i].l,qry[i].r);
    }
}

int answer[MAX];

void solve(){
    v[n+1]=INF;
    stack<int>stv;
    stv.push(n+1);
    int i;
    int id=1;
    for(i=n;i;--i){
        int val=v[i];
        while(v[stv.top()]<=val)
            stv.pop();
        aib.add_val(stv.top(),val+v[stv.top()]);
        stv.push(i);
        while(id<=q && qry[id].l==i){
            answer[qry[id].id]=aib.pref_max(qry[id].r);
            ++id;
        }
    }
}

void write(){
    int i;
    for(i=1;i<=q;++i)
        cout<<(chef[i]>=answer[i])<<'\n';
}

int main()
{
    read();
    rev_problem();
    solve();
    write();
    return 0;
}

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