oj.uz

Submission #147789

# Submission time Handle Problem Language Result Execution time Memory
147789 2019-08-30T16:19:29 Z theboatman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1604 ms 262144 KB 
#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, k, num;
};

struct tree {
    struct node {
        int mx, val, from;
    };

    vector <node> t1;
    vector <vector <int> > t;

    int v, tl, tr;

    void init(int n) {
        v = 1;
        tl = 0;
        tr = n - 1;

        t.resize(N * 4);
        t1.resize(N * 4);
    }

    void build(int v, int tl, int tr, vector <int> &a) {
        if (tl == tr) {
            t[v].push_back(a[tl]);
            t1[v] = make_struct(a[tl], 0, v);
        }
        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);
            }

            int mx = 0;
            for(auto i : t[v]) {
                mx = max(mx, i);

                if (mx > i) {
                    t1[v].val = max(t1[v].val, mx + i);
                }
            }

            sort(t[v].begin(), t[v].end());
            t1[v].mx = t[v].back();
            t1[v].from = v;
        }
    }

    void build(vector <int> &a) {
        build(v, tl, tr, a);
    }

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

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

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

        if (ql.val == -1) {
            return qr;
        }

        if (qr.val == -1) {
            return ql;
        }

        int mx = max(ql.mx, qr.mx);
        int from = qr.from;

        int flag = 0;
        if (from == -1) {
            from++;
            flag = 1;
        }

        int ind = lower_bound(t[from].begin(), t[from].end(), mx) - t[from].begin() - 1;

        if (flag) {
            ind = -1;
        }

        int val = max(ql.val, qr.val);
        if (ind != -1) {
            val = max(val, t[from][ind] + mx);
        }

        return make_struct(mx, val, -1);
    }

    int get(int l, int r) {
        return get(v, tl, tr, l, r).val;
    }
};

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

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

    vector <int> a(n);
    for(auto &i : a) {
        cin >> i;
    }

    vector <osu> b(m);
    for(auto &i : b) {
        cin >> i.l >> i.r >> i.k;
        i.l--, i.r--;
    }

    tree str;
    str.init(n);
    str.build(a);

    for(auto &i : b) {
        cout << (str.get(i.l, i.r) <= i.k) << "\n";
    }

    return 0;
}

/*
*/

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1604 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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