Submission #890683

#	Time	Username	Problem	Language	Result	Execution time	Memory
890683		NotLinux	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	974 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int M = 4e6 + 7;
const int inf = 2e9 + 7;
// bool debug_mode = 0;
struct MergeSortTree{
    vector < int > tree[M];
    void build(vector < int > &v , int ind=1 , int l=1 , int r=N){
        for(int i = l-1;i<r;i++){
            tree[ind].push_back(v[i]);
        }
        sort(tree[ind].begin() , tree[ind].end());
        if(l != r){
            int mid = (l+r) >> 1;
            build(v , ind*2 , l , mid);
            build(v , ind*2+1 , mid+1 , r);
        }
    }
    inline int query(int ind , int val){
        auto it = lower_bound(tree[ind].begin() , tree[ind].end() , val);
        int res = -1;
        if(it != tree[ind].begin()){
            res = *(--it);
        }
        // if(debug_mode){
        //     cout << "v : ";for(auto itr : tree[ind])cout << itr << " ";cout << endl;
        //     cout << "val : " << val << endl;
        //     cout << "res : " << res << endl;
        // }
        return res;
    }
} mst;
struct SegmentTree{
    struct Node{
        int mx=0 , indx=0 , ans=-inf;
    } tree[M];
    Node merge(Node &a , Node &b){
        Node c;
        c.mx = max(a.mx , b.mx);
        int tmp = mst.query(b.indx , a.mx);
        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 , int ind=1 , int l=1 , int r=N){
        for(int i = l-1;i<r;i++){
            tree[ind].mx = max(tree[ind].mx , v[i]);
        }
        if(l != r){
            int mid = (l+r) >> 1;
            build(v , ind*2 , l , mid);
            build(v , ind*2+1 , mid+1 , r);
            tree[ind] = merge(tree[ind*2] , tree[ind*2+1]);
        }
        tree[ind].indx = ind;
        // cout << l << " " << r << " => " << tree[ind].mx << " " << tree[ind].ans << endl;
    }
    vector < Node > vec;
    void dfs(int ql , int qr , int ind=1 , int l=1 , int r=N){
        if(l >= ql and r <= qr){
            // cout << l << " " << r << " : " << tree[ind].mx << " " << tree[ind].ans << endl;
            vec.push_back(tree[ind]);
        }
        else if(l > qr or r < ql){
            return;
        }
        else{
            int mid = (l+r) >> 1;
            dfs(ql , qr , ind*2 , l , mid);
            dfs(ql , qr , ind*2+1 , mid+1 , r);
        }
    }
    int query(int l , int r){
        Node ret;
        // debug_mode = 1;
        for(auto itr : vec){
            ret = merge(ret , itr);
            // cout << ret.mx << " " << ret.ans << endl;
        }
        // debug_mode = 0;
        vec.clear();
        // cout << "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];
    }
    mst.build(arr,1,1,arr.size());
    segt.build(arr,1,1,arr.size());
    // cout << "---" << endl;
    for(int qt = 0;qt<m;qt++){
        int l,r,k;
        cin >> l >> r >> k;
        segt.dfs(l,r,1,1,arr.size());
        cout << (segt.query(l,r) <= k) << '\n';
        // cout << "---" << endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int testcase = 1;//cin >> testcase;
    while(testcase--)solve();
}

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