Submission #956460

#	Time	Username	Problem	Language	Result	Execution time	Memory
956460		Darren0724	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	81 ms	10976 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=10005;
const int INF=1e9;
vector<int> t;
struct segtree{
    struct seg{
        vector<int> v;
        int val=0;
    }tr[N<<2];
    seg merge(seg a,seg b){
        seg ans;
        ans.val=max(a.val,b.val);
        auto &c=a.v,&d=b.v;
        int ptr1=0,ptr2=0;
        while(ptr1<c.size()&&ptr2<d.size()){
            if(c[ptr1]<=d[ptr2]){
                if(ptr2>0)ans.val=max(ans.val,c[ptr1]+d[ptr2-1]);
                ans.v.push_back(c[ptr1++]);
            }
            else{
                ans.v.push_back(d[ptr2++]);
            }
        }
        while(ptr1<c.size()){
            if(ptr2>0)ans.val=max(ans.val,c[ptr1]+d[ptr2-1]);
            ans.v.push_back(c[ptr1++]);
        }
        while(ptr2<d.size()){
            ans.v.push_back(d[ptr2++]);
        }
        return ans;
    }
    void build(vector<int> &a,int id,int l,int r){
        if(r-l==1){
            tr[id].v.push_back(a[l]);
            return;        
        }
        int m=(l+r)>>1;
        build(a,id<<1,l,m);
        build(a,id<<1|1,m,r);
        tr[id]=merge(tr[id<<1],tr[id<<1|1]);
    }
    void ask(int id,int a,int b,int l,int r){
        if(a<=l&&b>=r)return t.push_back(id);
        int m=(l+r)>>1;
        if(a<m)ask(id<<1,a,b,l,m);
        if(b>m)ask(id<<1|1,a,b,m,r);
    }
};
int32_t main() {
    LCBorz;
    int n,q;cin>>n>>q;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    segtree st;
    st.build(v,1,0,n);
    for(int i=0;i<q;i++){
        int l,r,c;cin>>l>>r>>c;
        t.clear();
        st.ask(1,l-1,r,0,n);
        int m=t.size();
        int mx=0;
        int ans=0;
        for(int j=0;j<m;j++){
            int f=t[j];
            auto &c=st.tr[f].v;
            ans=max(ans,st.tr[f].val);
            if(mx>c[0]){
                int t=lower_bound(all(c),mx)-c.begin()-1;
                ans=max(ans,mx+c[t]);
            }
            mx=max(mx,c.back());
        }
        cout<<(ans<=c)<<endl;
    }
    
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In member function 'segtree::seg segtree::merge(segtree::seg, segtree::seg)':
sortbooks.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         while(ptr1<c.size()&&ptr2<d.size()){
      |               ~~~~^~~~~~~~~
sortbooks.cpp:19:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         while(ptr1<c.size()&&ptr2<d.size()){
      |                              ~~~~^~~~~~~~~
sortbooks.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         while(ptr1<c.size()){
      |               ~~~~^~~~~~~~~
sortbooks.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         while(ptr2<d.size()){
      |               ~~~~^~~~~~~~~

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