Submission #291952

#	Time	Username	Problem	Language	Result	Execution time	Memory
291952		dantoh000	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2158 ms	161400 KiB

sortbooks

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int, int> iiii;
int n,m;
ii p[1000005];
int ans[1000005];
int w[1000005];
vector<ii> st;
iiii q[1000005];
struct node{
    int s,e,m,v;
    node *l, *r;
    node (int _s, int _e): s(_s), e(_e){
        m = (s+e)/2;
        v = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void up(int x, int nv){
        if (s == e) {
            v = max(v,nv);
            return;
        }
        if (x > m) r->up(x,nv);
        else if (x <= m) l->up(x,nv);
        v = max(l->v,r->v);
    }
    int qu(int qs ,int qe){
        if (qs == s && qe == e) return v;
        if (qs > m) return r->qu(qs,qe);
        else if (qe <= m) return l->qu(qs,qe);
        else return max(l->qu(qs,m),r->qu(m+1,qe));
    }
} *root;
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++) {
        scanf("%d",&w[i]);
        while (st.size() && st.back().fi <= w[i]) st.pop_back();
        if (st.size()) p[i] = {st.back().fi + w[i], st.back().se};
        else p[i] = {0,1};
        st.push_back({w[i],i});
    }
    root = new node(1,n);
    int l,r,k;
    for (int i = 0; i < m; i++){
        scanf("%d%d%d",&l,&r,&k);
        q[i] = {r,l,k,i};
    }
    int cur = 0;
    sort(q,q+m);
    for (int i = 0; i < m; i++){
        int l,r,k,id;
        tie(r,l,k,id) = q[i];
        while (cur <= r){
            root->up(p[cur].se, p[cur].fi);
            cur++;
        }

        ans[id] = (root->qu(l,r) <= k);
    }

    for (int i = 0; i < m; i++){
        printf("%d\n",ans[i]);
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~
sortbooks.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d%d%d",&l,&r,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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