Submission #908674

#	Time	Username	Problem	Language	Result	Execution time	Memory
908674		SalihSahin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	2704 ms	262144 KiB

sortbooks

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

struct node{
    int mx, calc;
    node(){
        mx = calc = 0;
    }
};

node merge(node a, node b, vector<int> &arr){
    node res;
    res.mx = max(a.mx, b.mx);
    res.calc = max(a.calc, b.calc);
    if(arr[0] < a.mx){
        auto x = lower_bound(arr.begin(), arr.end(), a.mx) - arr.begin();
        x--;
        res.calc = max(res.calc, arr[x] + a.mx);
    }

    return res;
}

struct SEGT{
    vector<node> tree;
    vector<vector<int> > list;
    int S;

    void init(int n){
        tree.assign(4*n, node());
        list.resize(4*n);
        S = n;
    }

    void build(int ind, int l, int r, vector<int> &a){
        if(l == r){
            list[ind].pb(a[l]);
            tree[ind].mx = a[l];
        }
        else{
            int m = (l + r)/2;

            build(ind*2, l, m, a);
            build(ind*2+1, m+1, r, a);

            int il = 0, ir = 0;
            while(il < list[ind*2].size() && ir < list[ind*2+1].size()){
                if(list[ind*2][il] <= list[ind*2+1][ir]){
                    list[ind].pb(list[ind*2][il]);
                    il++;
                }
                else{
                    list[ind].pb(list[ind*2+1][ir]);
                    ir++;
                }
            }
            while(il < list[ind*2].size()){
                list[ind].pb(list[ind*2][il]);
                il++;
            }
            while(ir < list[ind*2+1].size()){
                list[ind].pb(list[ind*2+1][ir]);
                ir++;
            }

            tree[ind] = merge(tree[ind*2], tree[ind*2+1], list[ind*2+1]);
        }
    }

    int querylist(int ind, int l, int r, int ql, int qr, int k){
        if(l > r || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr){
            if(list[ind][0] >= k) return 0;

            auto x = lower_bound(list[ind].begin(), list[ind].end(), k) - list[ind].begin();
            x--;
            return list[ind][x];
        }
        else{
            int m = (l + r)/2;
            return max(querylist(ind*2, l, m, ql, qr, k), querylist(ind*2+1, m+1, r, ql, qr, k));            
        }
    }

    int query(int ind, int l, int r, int ql, int qr){
        if(l > r || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr){

            int gh = querylist(1, 1, S, r, qr, tree[ind].mx);
            int val = tree[ind].calc;
            if(gh != 0 && tree[ind].mx > gh){
                val = max(val, tree[ind].mx + gh);
            }

            return val;
        }
        else{
            int m = (l + r)/2;
            return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));            
        }
    }
};
 
int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, q;
    cin>>n>>q;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    SEGT seg;
    seg.init(n);
    seg.build(1, 1, n, a);

    while(q--){
        int l, r, k;
        cin>>l>>r>>k;

        int val = seg.query(1, 1, n, l, r);
        if(val <= k) cout<<1<<endl;
        else cout<<0<<endl;
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void SEGT::build(int, int, int, std::vector<int>&)':
sortbooks.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             while(il < list[ind*2].size() && ir < list[ind*2+1].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:52:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             while(il < list[ind*2].size() && ir < list[ind*2+1].size()){
      |                                              ~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             while(il < list[ind*2].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             while(ir < list[ind*2+1].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~

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