Submission #683389

#	Time	Username	Problem	Language	Result	Execution time	Memory
683389		FatihSolak	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1167 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int a[N];
int ans[N];
struct node{
    int val = 0,maxi = -1;
};
struct node2{
    int l = 0,r = 0, val = 0;
}tree[N*20];
vector<pair<int,int>> roots;
int cnt = 1;
int upd(int v,int tl,int tr,int pos,int val){
    if(tl == tr){
        int nw = ++cnt;
        tree[nw].val = tree[v].val + val;
        return nw;
    }
    int tm = (tl + tr)/2;
    if(pos <= tm){
        int nw = ++cnt;
        tree[nw].l = upd(tree[v].l,tl,tm,pos,val);
        tree[nw].r = tree[v].r;
        tree[nw].val = tree[tree[nw].l].val +  tree[tree[nw].r].val;
        return nw;
    }
    else{
        int nw = ++cnt;
        tree[nw].l = tree[v].l;
        tree[nw].r = upd(tree[v].r,tm+1,tr,pos,val);
        tree[nw].val = tree[tree[nw].l].val +  tree[tree[nw].r].val;
        return nw;
    }
}
int gett(int v,int tl,int tr,int l,int r){
    if(r < tl || tr < l){
        return 0;
    }
    if(l <= tl && tr <= r){
        return tree[v].val;
    }
    int tm = (tl + tr)/2;
    return gett(tree[v].l,tl,tm,l,r) + gett(tree[v].r,tm+1,tr,l,r);
}
struct SegTree{
    vector<node> t;
    int n;
    int k;
    SegTree(int sz){
        n = sz;
        t.assign(4*n,{0,-1});
        build(1,1,n);
    }
    node merge(node a,node b){
        node ret;
        ret.val = max(a.val,b.val);
        ret.maxi = max(a.maxi,b.maxi);
        return ret;
    }
    void build(int v,int tl,int tr){
        if(tl == tr){
            t[v].maxi = a[tl];
            return;
        }
        int tm = (tl + tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        t[v] = merge(t[v*2],t[v*2+1]);
        for(int i = tm+1;i<=tr;i++){
            if(a[i] < t[v*2].maxi){
                t[v].val = max(t[v].val,t[v*2].maxi + a[i]);
            }
        }
    }
    node get(int v,int tl,int tr,int l,int r){
        if(tr < l || r < tl){
            return {0,-1};
        }
        if(l <= tl && tr <= r){
            return t[v];
        }
        int tm = (tl + tr)/2;
        node a = get(v*2,tl,tm,l,r);
        node b = get(v*2+1,tm+1,tr,l,r);
        int num = k+1 - a.maxi;
        if(num < a.maxi){
            int cnt = 0;
            int idx = lower_bound(roots.begin(),roots.end(),make_pair(num,0),greater<pair<int,int>>()) - roots.begin();
            if(idx != roots.size())
                cnt += gett(roots[idx].second,1,n,max(l,tm+1),min(r,tr));
            idx = lower_bound(roots.begin(),roots.end(),make_pair(a.maxi,0),greater<pair<int,int>>()) - roots.begin();
            if(idx != roots.size())
                cnt -= gett(roots[idx].second,1,n,max(l,tm+1),min(r,tr));
            if(cnt)
                a.val = k+1;
        }
        return merge(a,b);
    }
    node get(int l,int r,int kk){
        k = kk;
        return get(1,1,n,l,r);
    }
};
struct SegTree2{
    vector<int> t;
    int n;
    SegTree2(int sz){
        n = sz;
        t.assign(4*n,1e9);
    }
    void upd(int v,int tl,int tr,int pos,int val){
        if(tl == tr){
            t[v] = min(t[v],val);
            return;
        }
        int tm = (tl + tr)/2;
        if(pos <= tm){
            upd(v*2,tl,tm,pos,val);
        }
        else upd(v*2+1,tm+1,tr,pos,val);
        t[v] = min(t[v*2],t[v*2+1]);
    }
    int get(int v,int tl,int tr,int l,int r){
        if(tr < l || r < tl){
            return 1e9;
        }
        if(l <= tl && tr <= r){
            return t[v];
        }
        int tm = (tl + tr)/2;
        return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
    }
    void upd(int pos,int val){
        upd(1,1,n,pos,val);
    }
    int get(int l,int r){
        return get(1,1,n,l,r);
    }
};
void solve(){
    int n,m;
    cin >> n >> m;
    vector<int> cmp;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        cmp.push_back(i);
    }
    sort(cmp.begin(),cmp.end(),[&](int x,int y){
        return a[x] > a[y];
    });
    roots.push_back({-1,1});
    for(auto u:cmp){
        int tmp = roots.back().second;
        if(roots.back().first == u)
            roots.pop_back();
        roots.push_back({a[u],upd(tmp,1,n,u,1)});
    }
    SegTree t(n);
    for(int i = 1;i<=m;i++){
        int l,r,k;
        cin >> l >> r >> k;
        ans[i] = t.get(l,r,k).val <= k;
    }
    for(int i = 1;i<=m;i++){
        cout << ans[i] << '\n';
    }
}
    
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

sortbooks.cpp: In member function 'node SegTree::get(int, int, int, int, int)':
sortbooks.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             if(idx != roots.size())
      |                ~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             if(idx != roots.size())
      |                ~~~~^~~~~~~~~~~~~~~

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