Submission #890719

#	Time	Username	Problem	Language	Result	Execution time	Memory
890719		NotLinux	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2597 ms	255228 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 20) + 7;
const int inf = 2e9 + 7;
// bool debug_mode = 0;
inline int closest(vector < int > &v , int x){
    auto it = lower_bound(v.begin() , v.end() , x);
    if(it == v.begin()){
        return -1;
    }
    else{
        return *(--it);
    }
}
struct MergeSortTree{
    vector < int > tree[2*N];
    int sz;
    void merge(vector < int > &a , vector < int > &b , vector < int > &c){
        int pa = 0 , pb = 0;
        while(pa != (int)a.size() or pb != (int)b.size()){
            if(pa == (int)a.size()){
                c.push_back(b[pb++]);
            }
            else if(pb == (int)b.size()){
                c.push_back(a[pa++]);
            }
            else{
                if(a[pa] < b[pb]){
                    c.push_back(a[pa++]);
                }
                else{
                    c.push_back(b[pb++]);                    
                }
            }
        }
    }
    void build(vector < int > &v){
        for(int i = sz;i<2*sz;i++){
            tree[i].push_back(v[i-sz]);
        }
        for(int i = sz-1;i>0;i--){
            // cerr << i << " : ";
            // for(auto itr : tree[i<<1])cout << itr << " ";
            // cerr << "|| ";
            // for(auto itr : tree[i<<1|1])cout << itr << " ";
            // cerr << endl;
            merge(tree[i<<1] , tree[i<<1|1] , tree[i]);
            // cerr << "res : ";for(auto itr : tree[i])cout << itr << " ";cout << endl;
        }
    }
    inline int query(int ind , int val){
        return closest(tree[ind] , val);
    }
} mst;
struct SegmentTree{
    struct Node{
        int mx=0 , indx=0 , ans=-inf;
    } tree[2*N];
    int sz;
    Node merge(Node &a , Node &b){
        Node c;
        c.mx = max(a.mx , b.mx);
        int tmp = mst.query(b.indx , a.mx);
        // cerr << "b : ";for(auto itr : mst.tree[b.indx])cout << itr << " ";cout << endl;
        if(tmp != -1){
            c.ans = max({a.ans , b.ans , (int)a.mx + (int)tmp});
        }
        else {
            c.ans = max(a.ans , b.ans);
        }
        return c;
    }
    void build(vector < int > &v){
        for(int i = sz;i<2*sz;i++){
            tree[i].mx = v[i-sz];
            tree[i].indx = i;
        }
        for(int i = sz-1;i>0;i--){
            tree[i] = merge(tree[i << 1] , tree[i << 1|1]);
            tree[i].indx = i;
            // cerr << tree[i].indx << " : " << tree[i].mx << " " << tree[i].ans << endl;
        }
    }
    vector < Node > vec1 , vec2;
    void dfs(int ql , int qr){
        for(ql += sz , qr += sz; ql < qr;ql >>= 1 , qr >>= 1){
            if(ql&1){
                // cerr << "added : " << ql << endl;
                vec1.push_back(tree[ql++]);
            }
            if(qr&1){
                vec2.push_back(tree[--qr]);
                // cerr << "added : " << qr << endl;
            }
        }
    }
    int query(int l , int r){
        Node ret;
        // debug_mode = 1;
        reverse(vec2.begin() , vec2.end());
        for(auto itr : vec2)vec1.push_back(itr);
        for(auto itr : vec1){
            // cerr << itr.indx << " : " << itr.mx << " " << itr.ans << endl;
            ret = merge(ret , itr);
        }
        // debug_mode = 0;
        vec1.clear();
        vec2.clear();
        // cerr << "query : " << ret.ans << endl;
        return ret.ans;
    }
} segt;
void solve(){
    int n,m;
    cin >> n >> m;
    vector < int > arr(n);
    for(int i = 0;i<n;i++){
        cin >> arr[i];
    }

    int hsb = __lg(n);
    n = (1 << (hsb+1));
    while(arr.size() < n){
        arr.push_back(1e9);
    }

    mst.sz = segt.sz = n;
    mst.build(arr);
    segt.build(arr);
    // cerr << "---" << endl;
    for(int qt = 0;qt<m;qt++){
        int l,r,k;
        cin >> l >> r >> k;
        // cerr << "query : " << l << " " << r << endl;
        l--;
        segt.dfs(l,r);
        cout << (segt.query(l,r) <= k) << '\n';
        // cerr << "---" << endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int testcase = 1;//cin >> testcase;
    while(testcase--)solve();
}

Compilation message (stderr)

sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:123:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |     while(arr.size() < n){
      |           ~~~~~~~~~~~^~~

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