oj.uz

Submission #833096

# Submission time Handle Problem Language Result Execution time Memory
833096 2023-08-22T00:31:29 Z skittles1412 Comparing Plants (IOI20_plants) C++17
100 / 100
 850 ms 88620 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

struct ST1 {
    struct Node {
        int mx, ind;

        Node operator+(const Node& n) const {
            if (mx > n.mx) {
                return *this;
            }
            return n;
        }

        Node with_lazy(int x) const {
            return {mx + x, ind};
        }
    };

    int n;
    vector<Node> v, arr;
    vector<int> lazy;

    ST1(const vector<Node>& arr) : n(sz(arr)), v(4 * n), arr(arr), lazy(4 * n) {
        build(1, 0, n - 1);
    }

    void build(int o, int l, int r) {
        if (l == r) {
            v[o] = arr[l];
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        v[o] = v[lc] + v[rc];
    }

    void update(int o, int l, int r, int ql, int qr, int x) {
        if (ql <= l && r <= qr) {
            v[o].mx += x;
            lazy[o] += x;
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        }
        v[o] = (v[lc] + v[rc]).with_lazy(lazy[o]);
    }

    void update(int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    Node query_all() const {
        return v[1];
    }
};

struct DS2 {
    int n, m;
    set<int> v, good;

    DS2(int n, int m) : n(n), m(m) {}

    bool check(set<int>::iterator it) const {
        if (it == v.begin()) {
            if (sz(v) == 1) {
                return true;
            }
            return *it + n - *v.rbegin() >= m;
        }
        int cur = *it, prv = *(--it);
        return cur - prv >= m;
    }

    void check_update(set<int>::iterator it) {
        if (it == v.end()) {
            return;
        }

        if (check(it)) {
            good.insert(*it);
        } else {
            good.erase(*it);
        }
    }

    void insert(int x) {
        auto [it, inserted] = v.insert(x);
        assert(inserted);
        check_update(it);
        check_update(++it);
        check_update(v.begin());
    }

    void erase(int x) {
        bool erased = !!v.erase(x);
        assert(erased);
        good.erase(x);
        check_update(v.lower_bound(x));
        check_update(v.begin());
    }
};

vector<int> solve_layers(int m, const vector<int>& arr) {
    int n = sz(arr);

    ST1 st_arr(({
        vector<ST1::Node> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = {arr[i], i};
        }
        v;
    }));

    int ans_it = 0, ans_cnt = 0;
    vector<int> ans(n);

    DS2 m_imp(n, m);

    while (ans_cnt < n) {
        while (true) {
            auto it = st_arr.query_all();
            if (it.mx == m - 1) {
                m_imp.insert(it.ind);
                st_arr.update(it.ind, it.ind, -1e9);
            } else {
                break;
            }
        }

        vector<int> c_vals(begin(m_imp.good), end(m_imp.good));

        for (auto& cur : c_vals) {
            ans_cnt++;
            ans[cur] = ans_it;
            if (cur - m + 1 < 0) {
                st_arr.update(0, cur, +1);
                st_arr.update(cur - m + 1 + n, n - 1, +1);
            } else {
                st_arr.update(cur - m + 1, cur, +1);
            }

            m_imp.erase(cur);
        }

        ans_it++;
    }

    dbg(ans);
    return ans;
}

struct QConn {
    int n, logn, m;
    vector<int> layers;
    vector<vector<int>> lift;

    QConn() {}
    QConn(int m, const vector<int>& _layers)
        : n(sz(_layers)),
          logn(__lg(n) + 3),
          m(m),
          layers(_layers),
          lift(logn + 1, vector<int>(2 * n)) {
        auto tmp = layers;
        layers.insert(layers.end(), begin(tmp), end(tmp));

        map<int, int> q;
        for (int i = 2 * n - 1; i >= 0; i--) {
            if (i + m < 2 * n) {
                q.erase(layers[i + m]);
            }
            assert(!q.count(layers[i]));
            q[layers[i]] = i;

            auto it = q.upper_bound(layers[i]);
            if (it == q.end()) {
                lift[0][i] = -1;
            } else {
                lift[0][i] = it->second;
            }
        }

        for (int i = 1; i <= logn; i++) {
            for (int j = 0; j < 2 * n; j++) {
                if (lift[i - 1][j] == -1) {
                    lift[i][j] = -1;
                } else {
                    lift[i][j] = lift[i - 1][lift[i - 1][j]];
                }
            }
        }
    }

    bool query_lt(int u, int v) const {
        if (layers[u] >= layers[v]) {
            return false;
        }
        if (v < u) {
            v += n;
        }

        for (int i = logn; i >= 0; i--) {
            int nu = lift[i][u];
            if (nu != -1 && layers[nu] <= layers[v]) {
                u = nu;
            }
        }

        return v <= u;
    }
};

struct Solver {
    int n, m;
    vector<int> layers;
    QConn q_f, q_r;

    Solver() {}
    Solver(int m, const vector<int>& arr)
        : n(sz(arr)),
          m(m),
          layers(solve_layers(m, arr)),
          q_f(m, layers),
          q_r(m, reversed(layers)) {
        dbg(layers);
    }

    bool query_lt(int u, int v) const {
        return q_f.query_lt(u, v) || q_r.query_lt(n - u - 1, n - v - 1);
    }

    int query(int u, int v) const {
        if (query_lt(u, v)) {
            return -1;
        } else if (query_lt(v, u)) {
            return 1;
        }
        return 0;
    }
} solver;

void init(int m, vector<int> arr) {
    solver = Solver(m, arr);
}

int compare_plants(int u, int v) {
    return solver.query(u, v);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 43 ms 3020 KB Output is correct
7 Correct 90 ms 9820 KB Output is correct
8 Correct 462 ms 81752 KB Output is correct
9 Correct 483 ms 84444 KB Output is correct
10 Correct 461 ms 81556 KB Output is correct
11 Correct 461 ms 80988 KB Output is correct
12 Correct 522 ms 81212 KB Output is correct
13 Correct 529 ms 81500 KB Output is correct
14 Correct 397 ms 79856 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 59 ms 6036 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 564 KB Output is correct
10 Correct 65 ms 6000 KB Output is correct
11 Correct 88 ms 5800 KB Output is correct
12 Correct 68 ms 6264 KB Output is correct
13 Correct 56 ms 5996 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 59 ms 6036 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 564 KB Output is correct
10 Correct 65 ms 6000 KB Output is correct
11 Correct 88 ms 5800 KB Output is correct
12 Correct 68 ms 6264 KB Output is correct
13 Correct 56 ms 5996 KB Output is correct
14 Correct 105 ms 11160 KB Output is correct
15 Correct 789 ms 82584 KB Output is correct
16 Correct 111 ms 12124 KB Output is correct
17 Correct 848 ms 84964 KB Output is correct
18 Correct 743 ms 83440 KB Output is correct
19 Correct 645 ms 83900 KB Output is correct
20 Correct 798 ms 88620 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 59 ms 4908 KB Output is correct
4 Correct 619 ms 79064 KB Output is correct
5 Correct 730 ms 80736 KB Output is correct
6 Correct 719 ms 80372 KB Output is correct
7 Correct 766 ms 80608 KB Output is correct
8 Correct 801 ms 83464 KB Output is correct
9 Correct 729 ms 80528 KB Output is correct
10 Correct 599 ms 81028 KB Output is correct
11 Correct 539 ms 81488 KB Output is correct
12 Correct 440 ms 80228 KB Output is correct
13 Correct 676 ms 81636 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 11 ms 1236 KB Output is correct
8 Correct 11 ms 1236 KB Output is correct
9 Correct 11 ms 1236 KB Output is correct
10 Correct 11 ms 1236 KB Output is correct
11 Correct 11 ms 1236 KB Output is correct
12 Correct 12 ms 1236 KB Output is correct
13 Correct 10 ms 1284 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 574 ms 78596 KB Output is correct
7 Correct 659 ms 80208 KB Output is correct
8 Correct 707 ms 80328 KB Output is correct
9 Correct 770 ms 82648 KB Output is correct
10 Correct 401 ms 79552 KB Output is correct
11 Correct 513 ms 82008 KB Output is correct
12 Correct 528 ms 78680 KB Output is correct
13 Correct 498 ms 80008 KB Output is correct
14 Correct 694 ms 79452 KB Output is correct
15 Correct 648 ms 80412 KB Output is correct
16 Correct 494 ms 79192 KB Output is correct
17 Correct 486 ms 79384 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 43 ms 3020 KB Output is correct
7 Correct 90 ms 9820 KB Output is correct
8 Correct 462 ms 81752 KB Output is correct
9 Correct 483 ms 84444 KB Output is correct
10 Correct 461 ms 81556 KB Output is correct
11 Correct 461 ms 80988 KB Output is correct
12 Correct 522 ms 81212 KB Output is correct
13 Correct 529 ms 81500 KB Output is correct
14 Correct 397 ms 79856 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 59 ms 6036 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 4 ms 564 KB Output is correct
24 Correct 65 ms 6000 KB Output is correct
25 Correct 88 ms 5800 KB Output is correct
26 Correct 68 ms 6264 KB Output is correct
27 Correct 56 ms 5996 KB Output is correct
28 Correct 105 ms 11160 KB Output is correct
29 Correct 789 ms 82584 KB Output is correct
30 Correct 111 ms 12124 KB Output is correct
31 Correct 848 ms 84964 KB Output is correct
32 Correct 743 ms 83440 KB Output is correct
33 Correct 645 ms 83900 KB Output is correct
34 Correct 798 ms 88620 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 59 ms 4908 KB Output is correct
38 Correct 619 ms 79064 KB Output is correct
39 Correct 730 ms 80736 KB Output is correct
40 Correct 719 ms 80372 KB Output is correct
41 Correct 766 ms 80608 KB Output is correct
42 Correct 801 ms 83464 KB Output is correct
43 Correct 729 ms 80528 KB Output is correct
44 Correct 599 ms 81028 KB Output is correct
45 Correct 539 ms 81488 KB Output is correct
46 Correct 440 ms 80228 KB Output is correct
47 Correct 676 ms 81636 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 256 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 2 ms 340 KB Output is correct
54 Correct 11 ms 1236 KB Output is correct
55 Correct 11 ms 1236 KB Output is correct
56 Correct 11 ms 1236 KB Output is correct
57 Correct 11 ms 1236 KB Output is correct
58 Correct 11 ms 1236 KB Output is correct
59 Correct 12 ms 1236 KB Output is correct
60 Correct 10 ms 1284 KB Output is correct
61 Correct 55 ms 5324 KB Output is correct
62 Correct 98 ms 11940 KB Output is correct
63 Correct 552 ms 80840 KB Output is correct
64 Correct 768 ms 80228 KB Output is correct
65 Correct 850 ms 80984 KB Output is correct
66 Correct 710 ms 81348 KB Output is correct
67 Correct 805 ms 83356 KB Output is correct
68 Correct 673 ms 82096 KB Output is correct
69 Correct 613 ms 82816 KB Output is correct
70 Correct 710 ms 79716 KB Output is correct
71 Correct 770 ms 80792 KB Output is correct
72 Correct 777 ms 80372 KB Output is correct
73 Correct 687 ms 80448 KB Output is correct
74 Correct 593 ms 80944 KB Output is correct
75 Correct 618 ms 80344 KB Output is correct