Submission #978889

#	Time	Username	Problem	Language	Result	Execution time	Memory
978889		Sofiatpc	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1516 ms	82368 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

struct query{
    int r,k,id;
};
#define sz(v) (int)v.size()
const int MAXN = 1e6+5;
int w[MAXN], r[MAXN], ans[MAXN], mx[MAXN*4], mxs[MAXN*4];
vector<int> st;
vector<query> q[MAXN];
query temp; 

void build(int node, int l, int r){
    mxs[node] = -1;
    if(l==r){
        mx[node] = w[l];
        return;
    }

    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    build(e,l,mid); build(d,mid+1,r);
    mx[node] = max(mx[e],mx[d]);
}

int query(int node, int l, int r, int i, int j){
    if(j < l || r < i)return -1;
    if(i <= l && r <= j)return mx[node];
    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    return max(query(e,l,mid,i,j),query(d,mid+1,r,i,j));
}

void updateS(int node, int l, int r, int i, int x){
    if(i < l || r < i)return;
    if(l==r){
        mxs[node] = x;
        return;
    }

    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    updateS(e,l,mid,i,x); updateS(d,mid+1,r,i,x);
    mxs[node] = max(mxs[e],mxs[d]);
}

int queryS(int node, int l, int r, int i, int j){
    if(j < l || r < i)return -1;
    if(i <= l && r <= j)return mxs[node];
    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    return max(queryS(e,l,mid,i,j),queryS(d,mid+1,r,i,j));
}

int bb( int x){
    int l = 0, r = sz(st)-1;
    while(l!=r){
        int mid = (l+r)/2;
        if(st[mid] <= x)r = mid;
        else l = mid+1;
    }
    return st[l];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>w[i];
    build(1,1,n);

    for(int i = 1; i <= m; i++){
        int l;
        cin>>l>>temp.r>>temp.k;
        temp.id = i;
        q[l].push_back(temp);
    }

    for(int i = n; i >= 1; i--){
        int mx = -1;
        while(sz(st) > 0 && w[st.back()] <= w[i]){
            updateS(1,1,n,st.back(),0);
            mx = w[st.back()];
            st.pop_back();
        }
        if(mx >= 0)updateS(1,1,n,i,w[i]+mx);
        st.push_back(i);

        for(int j = 0; j < sz(q[i]); j++){
            //for(int z : st)cout<<z<<" "<<w[z]<<", "; cout<<"\n";
            int u = bb(q[i][j].r); 
            int a = queryS(1,1,n,i,u-1), b = query(1,1,n,u+1,q[i][j].r);
            //cout<<u<<" "<<a<<" "<<b<<"\n";
            if(b >= 0)b += w[u];

            ans[q[i][j].id] = ( max(a,b) <= q[i][j].k );
        }
    }

    for(int i = 1; i <= m; i++)cout<<ans[i]<<"\n";
    
}

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