Submission #167230

#	Time	Username	Problem	Language	Result	Execution time	Memory
167230		apostoldaniel854	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	963 ms	94980 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
typedef long long ll;

int n, m;

const int N = 1e6;

int w[1 + N];
int stk[1 + N];
vector <int> op[1 + N];

void prec () {
    int top = 0;
    for (int i = 1; i <= n; i++) {
        while (top && w[stk[top]] <= w[i])
            top--;
        if (top)
            op[stk[top]].pb (i);
        stk[++top] = i;
    }
}
struct Query {
    int l;
    int r;
    int mood;
    int index;
};

Query q[1 + N];

bool cmp (Query a, Query b) {
    return a.l > b.l;
}

int lsb (int x) {
    return x & -x;
}

int aib[1 + N];
int ans[1 + N];



void upd (int pos, int val) {
    while (pos <= n) {
        aib[pos] = max (aib[pos], val);
        pos += lsb (pos);
    }
}

int qry (int pos) {
    int ans = 0;
    while (pos) {
        ans = max (ans, aib[pos]);
        pos -= lsb (pos);
    }
    return ans;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }

    prec ();

    for (int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r >> q[i].mood;
        q[i].index = i;
    }

    sort (q + 1, q + m + 1, cmp);

    int l = n;
    for (int i = 1; i <= m; i++) {
        while (l >= q[i].l) {
            for (auto x : op[l])
                upd (x, w[x] + w[l]);
            l--;
        }
        ans[q[i].index] = (qry (q[i].r) <= q[i].mood);
    }

    for (int i = 1; i <= m; i++)
        cout << ans[i] << "\n";

    return 0;
}

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