Submission #956454

#	Time	Username	Problem	Language	Result	Execution time	Memory
956454		Darren0724	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	3108 ms	262144 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=1000005;
const int INF=1e9;
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]);
    }
    seg ask(int id,int a,int b,int l,int r){
        if(a<=l&&b>=r)return tr[id];
        int m=(l+r)>>1;
        if(b<=m)return ask(id<<1,a,b,l,m);
        if(a>=m)return ask(id<<1|1,a,b,m,r);
        return merge(ask(id<<1,a,b,l,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;
        segtree::seg t=st.ask(1,l-1,r,0,n);
        cout<<(t.val<=c)<<endl;
    }
    
    return 0;
}

Compilation message (stderr)

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