Submission #151142

#	Time	Username	Problem	Language	Result	Execution time	Memory
151142		theboatman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	937 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;

typedef long long ll;

const long long INF = 1e18 + 10;
const int inf = 1e9 + 10;
const int N = 1e6 + 10;

struct osu {
    int l, r, x;
};

vector <int> t[N * 4];
void build(int v, int tl, int tr, vector <pair <int, int> > &a) {
    if (tl == tr) {
        t[v].push_back(a[tl].second);
    }
    else {
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm, a);
        build(v * 2 + 1, tm + 1, tr, a);

        t[v] = t[v * 2];
        for(auto i : t[v * 2 + 1]) {
            t[v].push_back(i);
        }

        sort(t[v].begin(), t[v].end());
    }
}

int get(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) {
        return -1;
    }

    if (tl == l && tr == r) {
        int ind = lower_bound(t[v].begin(), t[v].end(), x + 1) - t[v].begin() - 1;
        if (ind < 0) {
            return -1;
        }
        else {
            return t[v][ind];
        }
    }

    int tm = (tl + tr) / 2;
    int ql = get(v * 2, tl, tm, l, min(r, tm), x);
    int qr = get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);

    return max(ql, qr);
}

void calc(int v, int tl, int tr, int l, int r, int x, int x1,  vector <int> &used, map <pair <int, int>, int> &cost) {
    if (l > r) {
        return;
    }

    if (tl == l && tr == r) {
        int stn = int(t[v].size()) - 1;

        while(stn > -1 && t[v][stn] >= x) {
            int R = t[v][stn], L = used[r];

            int val = cost[make_pair(L, R)];
            cost[make_pair(L, R)] = max(val, x1);

            stn--;
        }

        return;
    }

    int tm = (tl + tr) / 2;
    calc(v * 2, tl, tm, l, min(r, tm), x, x1, used, cost);
    calc(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, x, x1, used, cost);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector <int> st;
    vector <int> used(n, -1);
    vector <pair <int, int> > b;
    map <pair <int, int>, int> cost;

    for(int i = 0; i < n; i++) {
        while(st.size() && a[st.back()] < a[i]) {
            st.pop_back();
        }

        if (st.size()) {
            int l = st.back(), r = i;

            b.push_back(make_pair(l, r));
            cost[make_pair(l, r)] = a[l] + a[r];

            used[r] = l;
        }

        st.push_back(i);
    }

    sort(b.begin(), b.end());

    if (!b.size()) {
        for(int i = 0; i < m; i++) {
            int l, r, k;
            cin >> l >> r >> k;

            cout << "1\n";
        }
        return 0;
    }

    build(1, 0, int(b.size()) - 1, b);

    for(int i = 1; i < b.size(); i++) {
        int ind = lower_bound(b.begin(), b.end(), make_pair(b[i].first + 1, -inf)) - b.begin() - 1;
        calc(1, 0, int(b.size()) - 1, 0, ind, b[i].second, cost[make_pair(b[i].first, b[i].second)], used, cost);
    }

    for(int i = 0; i < m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        l--, r--;

        int ind = lower_bound(b.begin(), b.end(), make_pair(l, -inf)) - b.begin();

        int x = 0;
        if (ind != b.size()) {
            r = get(1, 0, int(b.size()) - 1, ind, int(b.size()) - 1, r);

            if (r != -1) {
                x = cost[make_pair(used[r], r)];
            }
        }

        cout << (x <= k) << "\n";
    }
    return 0;
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3

5 2
1 2 3 5 4

*/

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:132:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < b.size(); i++) {
                    ~~^~~~~~~~~~
sortbooks.cpp:145:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ind != b.size()) {
             ~~~~^~~~~~~~~~~

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