Submission #1210831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210831		vanea	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	3095 ms	258440 KiB

sortbooks

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

const int mxN = 4e6+10;

array<int, 3> st[mxN];
int n;
vector<int> st1[mxN];

array<int, 3> comb(array<int, 3> &a, array<int, 3> &b, int left, int right) {
    array<int, 3> ans = {0, 0, 0};
    ans[0] = max(a[0], b[0]);
    if(a[2] > b[1]) {
        auto it = lower_bound(st1[right].begin(), st1[right].end(), a[2]);
        --it;
        ans[0] = max(ans[0], a[2]+(*it));
    }
    ans[1] = min(a[1], b[1]);
    ans[2] = max(a[2], b[2]);
    return ans;
}

void build(int node, int l, int r, vector<int> &v) {
    if(l == r) {
        st[node] = {0, v[l], v[l]};
        st1[node].push_back(v[l]);
        return ;
    }
    int mid = (l+r)/2;
    build(node*2, l, mid, v);
    build(node*2+1, mid+1, r, v);
    int i = 0, j = 0;
    while(i < st1[node*2].size() && j < st1[node*2+1].size()) {
        if(st1[node*2][i] <= st1[node*2+1][j]) {
            st1[node].push_back(st1[node*2][i++]);
        }
        else {
            st1[node].push_back(st1[node*2+1][j++]);
        }
    }
    while(i < st1[node*2].size()) {
        st1[node].push_back(st1[node*2][i++]);
    }
    while(j < st1[node*2+1].size()) {
        st1[node].push_back(st1[node*2+1][j++]);
    }
    st[node] = comb(st[node*2], st[node*2+1], node*2, node*2+1);
}

int qry1(int node, int l, int r, int l1, int r1) {
    if(l1 <= l && r <= r1) return st[node][2];
    if(l1 > r || r1 < l) return -1;
    int mid = (l+r)/2;
    return max(qry1(node*2, l, mid, l1, r1),
               qry1(node*2+1, mid+1, r, l1, r1));
}

int qry2(int node, int l, int r, int l1, int r1) {
    if(l1 <= l && r <= r1) return st[node][0];
    if(l1 > r || r1 < l) return 0;
    int mid = (l+r)/2;
    return max(qry1(node*2, l, mid, l1, r1),
               qry1(node*2+1, mid+1, r, l1, r1));
}

bool qry(int node, int l, int r, int l1, int r1, int k) {
    if(l1 <= l && r <= r1) {
        if(st[node][0] > k) return true;
        int x = qry1(1, 0, n-1, l1, l-1);
        if(x == -1) return false;
        auto it = upper_bound(st1[node].begin(), st1[node].end(), k-x);
        if(it == st1[node].end()) return false;
        if(*it >= x) return false;
        return true;
    }
    if(l1 > r || r1 < l) return false;
    int mid = (l+r)/2;
    bool lft = qry(node*2+1, mid+1, r, l1, r1, k);
    if(lft == true) return true;
    return qry(node*2, l, mid, l1, r1, k);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q;
    cin >> n >> q;
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    build(1, 0, n-1, v);
    while(q--) {
        int l, r, k;
        cin >> l >> r >> k;
        --l; --r;
        //int mx = qry2(1, 0, n-1, l, r);
        //if(mx > k) {
          //  cout << 0 << '\n';
          //  continue;
        //}
        bool ans = qry(1, 0, n-1, l, r, k);
        cout << 1-(int)ans << '\n';
    }
    return 0;
}

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