oj.uz

Submission #152809

# Submission time Handle Problem Language Result Execution time Memory
152809 2019-09-09T15:51:08 Z theboatman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1254 ms 50372 KB 
#include <bits/stdc++.h>

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

using namespace std;

struct tree {
    int v, tl, tr;
    vector <int> t;

    void init(int n) {
        t.resize(n * 4);

        v = 1;
        tl = 0, tr = n - 1;
    }

    void modify(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            t[v] = max(t[v], val);
        }
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) {
                modify(v * 2, tl, tm, pos, val);
            }
            else {
                modify(v * 2 + 1, tm + 1, tr, pos, val);
            }

            t[v] = max(t[v * 2], t[v * 2 + 1]);
        }
    }

    void modify(int pos, int val) {
        modify(v, tl, tr, pos, val);
    }

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

        if (tl == l && tr == r) {
            return t[v];
        }

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

        return max(ql, qr);
    }

    int get_suff(int l) {
        return get(v, tl, tr, l, tr);
    }
};

struct Query {
    int l, r, k, ind;
};

bool cmpQuery(Query a, Query b) {
    return a.r < b.r;
}

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 <Query> b(m);
    for(int i = 0; i < m; i++) {
        cin >> b[i].l >> b[i].r >> b[i].k;
        b[i].l--, b[i].r--;

        b[i].ind = i;
    }

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

    tree t;
    t.init(n);

    int r = 0;
    vector <int> stak, ans(m);

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

        if (stak.size()) {
            int l = stak.back();
            int x = a[l] + a[i];

            t.modify(l, x);
            while(r < m && b[r].r < i) {
                r++;
            }

            if (r != m) {
                ans[b[r].ind] = max(ans[b[r].ind], t.get_suff(b[r].l));
            }
        }

        stak.push_back(i);
    }

    for(int i = r; i < m; i++) {
        ans[b[i].ind] = max(ans[b[i].ind], t.get_suff(b[i].l));
    }

    for(int i = 0; i < m; i++) {
        ans[b[i].ind] = (ans[b[i].ind] <= b[i].k);
    }

    for(int i = 0; i < m; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}
/*
*/

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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