Submission #167229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167229	2019-12-06T20:57:31 Z	apostoldaniel854	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	974 ms	100232 KB

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;
}

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



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

ll qry (int pos) {
    ll ans = 0;
    while (pos) {
        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
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23804 KB	Output is correct
2	Correct	24 ms	23928 KB	Output is correct
3	Incorrect	26 ms	23932 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23804 KB	Output is correct
2	Correct	24 ms	23928 KB	Output is correct
3	Incorrect	26 ms	23932 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	928 ms	73392 KB	Output is correct
2	Correct	974 ms	100232 KB	Output is correct
3	Correct	964 ms	98268 KB	Output is correct
4	Correct	958 ms	98296 KB	Output is correct
5	Correct	818 ms	74104 KB	Output is correct