oj.uz

Submission #167228

# Submission time Handle Problem Language Result Execution time Memory
167228 2019-12-06T20:47:54 Z apostoldaniel854 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 933 ms 102628 KB 
#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 = m; i > 0; 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 25 ms 23928 KB Output is correct
2 Correct 39 ms 23928 KB Output is correct
3 Incorrect 25 ms 23928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 933 ms 102628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 30840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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