oj.uz

Submission #147760

# Submission time Handle Problem Language Result Execution time Memory
147760 2019-08-30T15:11:22 Z theboatman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 1542 ms 65128 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;
};

struct group3 {
    struct node {
        int ok, l, r;
    };

    int n, tl, tr, v;
    vector <node> t;

    void init(int _n) {
        n = _n;

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

        t.resize(n * 4);
    }

    node combine(node a, node b) {
        node res;

        res.ok = (a.ok & b.ok);
        res.ok &= (a.r <= b.l);

        res.l = a.l;
        res.r = b.r;

        return res;
    }

    void build(int v, int tl, int tr, vector <int> &a) {
        if (tl == tr) {
            t[v] = make_struct(1, a[tl], a[tr]);
        }
        else {
            int tm = (tl + tr) / 2;
            build(v * 2, tl, tm, a);
            build(v * 2 + 1, tm + 1, tr, a);

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

    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 t[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.ok == -1) {
            return qr;
        }

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

        return combine(ql, qr);
    }

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

vector <int> lg;
vector <vector <int> > table;

int get(int l, int r) {
    int len = (r - l + 1);
    len = lg[len];

    return max(table[len][r], table[len][l + (1 << len) - 1]);
}

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

    int flag = 1;
    int mn = *min_element(a.begin(), a.end());

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

        flag &= (i.k < mn);
    }

    if (flag) {
        group3 str;

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

        for(auto &i : b) {
            cout << str.get(i.l, i.r) << "\n";
        }
    }
    else {
        lg.resize(n + 1);
        int st = 1, res = 0;

        for(int i = 1; i <= n; i++) {
            lg[i] = res;

            if (i >= st * 2) {
                st *= 2;
                res++;
            }
        }

        table.resize(20, vector <int> (n));
        for(int st = 0; st < 20; st++) {
            if (!st) {
                for(int i = 0; i < n; i++) {
                    table[st][i] = a[i];
                }
            }
            else {
                for(int i = 0; i < n; i++) {
                    int l = i - (1 << (st - 1));

                    if (l >= 0) {
                        table[st][i] = max(table[st - 1][l], table[st - 1][i]);
                    }
                }
            }
        }

        if (n <= 5000 && m <= 5000) {
            for(auto i : b) {
                int flag = 1;
                for(int j = i.l; j <= i.r; j++) {
                    int mx = get(i.l, j);

                    if (mx > a[j]) {
                        flag &= (mx + a[j] <= i.k);
                    }
                }

                cout << flag << "\n";
            }
        }
    }
    return 0;
}

/*
*/

Subtask #1
8.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 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct

Subtask #2
9.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 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 11 ms 476 KB Output is correct
12 Correct 24 ms 760 KB Output is correct
13 Correct 28 ms 884 KB Output is correct
14 Correct 43 ms 888 KB Output is correct
15 Correct 45 ms 924 KB Output is correct
16 Correct 75 ms 888 KB Output is correct
17 Correct 59 ms 892 KB Output is correct
18 Correct 76 ms 924 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1499 ms 65096 KB Output is correct
2 Correct 1523 ms 65128 KB Output is correct
3 Correct 1531 ms 65072 KB Output is correct
4 Correct 1526 ms 65080 KB Output is correct
5 Correct 1542 ms 65004 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 10596 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 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 11 ms 476 KB Output is correct
12 Correct 24 ms 760 KB Output is correct
13 Correct 28 ms 884 KB Output is correct
14 Correct 43 ms 888 KB Output is correct
15 Correct 45 ms 924 KB Output is correct
16 Correct 75 ms 888 KB Output is correct
17 Correct 59 ms 892 KB Output is correct
18 Correct 76 ms 924 KB Output is correct
19 Incorrect 135 ms 20728 KB Output isn't correct
20 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 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 11 ms 476 KB Output is correct
12 Correct 24 ms 760 KB Output is correct
13 Correct 28 ms 884 KB Output is correct
14 Correct 43 ms 888 KB Output is correct
15 Correct 45 ms 924 KB Output is correct
16 Correct 75 ms 888 KB Output is correct
17 Correct 59 ms 892 KB Output is correct
18 Correct 76 ms 924 KB Output is correct
19 Correct 1499 ms 65096 KB Output is correct
20 Correct 1523 ms 65128 KB Output is correct
21 Correct 1531 ms 65072 KB Output is correct
22 Correct 1526 ms 65080 KB Output is correct
23 Correct 1542 ms 65004 KB Output is correct
24 Incorrect 55 ms 10596 KB Output isn't correct
25 Halted 0 ms 0 KB -