제출 #1156463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156463		Sir_Ahmed_Imran	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	2461 ms	242020 KiB

sortbooks

                //    01001100 01001111 01010100 01000001    \\
                //                                           \\
                //                ╦  ╔═╗╔╦╗╔═╗               \\
                //                ║  ║ ║ ║ ╠═╣               \\
                //                ╩═╝╚═╝ ╩ ╩ ╩               \\
                //                                           \\
                //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;

#define N 1000001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int n, x;
int a[N];
int seg[N << 2];
vector<int> mst[N << 2];

int bs(int val, vector<int> & v){
    int p = 1;
    int ind = 0;
    if(val <= v[0]) return 0;
    while(p * 2 < v.size()) p *= 2;
    for(int i = p; i > 0; i /= 2)
        if(ind + i < v.size() && v[ind + i] < val)
            ind += i;
    return val + v[ind];
}

void build(int v = 1, int s = 0, int e = n){
    if(e - s == 1){
        seg[v] = 0;
        mst[v] = {a[s]};
        return;
    }
    int mid, rc, lc, p, q;
    mid = (s + e) / 2;
    rc = 2 * v + 1;
    lc = 2 * v;
    p = q = 0;
    build(lc, s, mid);
    build(rc, mid, e);
    seg[v] = max(seg[lc], seg[rc]);
    seg[v] = max(seg[v], bs(mst[lc].back(), mst[rc]));
    while(p < mst[lc].size() && q < mst[rc].size()){
        mst[v].append(min(mst[lc][p], mst[rc][q]));
        if(mst[lc][p] < mst[rc][q]) p++;
        else q++;
    }
    for(int i = p; i < mst[lc].size(); i++)
        mst[v].append(mst[lc][i]);
    for(int i = q; i < mst[rc].size(); i++)
        mst[v].append(mst[rc][i]);
}

int get(int l, int r, int v = 1, int s = 0, int e = n){
    if(r <= s || e <= l) return 0;
    if(l <= s && e <= r){
        int ans = max(seg[v], bs(x, mst[v]));
        x = max(x, mst[v].back());
        return ans;
    }
    int mid, rc, lc;
    mid = (s + e) / 2;
    rc = 2 * v + 1;
    lc = 2 * v;
    return max(get(l, r, lc, s, mid), get(l, r, rc, mid, e));
}

void solve(){
    int m, o, l, r, k;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    build();
    while(m--){
        x = 0;
        cin >> l >> r >> k;
        cout << (get(l - 1, r) <= k) << nl;
    }
}    

int terminator(){
    L0TA;
    int T;
    solve();
    return 0;
}

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