Submission #1201952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201952		Triseedot	Comparing Plants (IOI20_plants)	C++20	44 / 100	357 ms	34132 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define len(v) (int) (v.size())
#define all(v) v.begin(), v.end()
using i32 = int;
//#define int long long

struct SegmentTree {
    int n;
    vector<pair<int, int>> tree;
    vector<int> push;
    const pair<int, int> NEUTRAL = {1e9, -1};

    void receive_update(int v, int upd) {
        tree[v].first += upd;
        push[v] += upd;
    }
    void do_push(int v) {
        receive_update(2 * v, push[v]);
        receive_update(2 * v + 1, push[v]);
        push[v] = 0;
    }

    void build(int v, int l, int r, vector<int>& a) {
        if (l + 1 == r) {
            tree[v] = {a[l], l};
            return;
        }
        int m = (l + r) / 2;
        build(2 * v, l, m, a);
        build(2 * v + 1, m, r, a);
        tree[v] = min(tree[2 * v], tree[2 * v + 1]);
    }
    SegmentTree(vector<int>& a) {
        n = len(a);
        tree.resize(4 * n);
        push.assign(4 * n, 0);
        build(1, 0, n, a);
    }

    void modify(int v, int l, int r, int ql, int qr, int upd) {
        if (r <= ql || qr <= l) return;
        if (ql <= l && r <= qr) {
            receive_update(v, upd);
            return;
        }
        do_push(v);
        int m = (l + r) / 2;
        modify(2 * v, l, m, ql, qr, upd);
        modify(2 * v + 1, m, r, ql, qr, upd);
        tree[v] = min(tree[2 * v], tree[2 * v + 1]);
    }
    void modify(int ql, int qr, int upd) {
        if (ql == qr) return;
        modify(1, 0, n, ql, qr, upd);
    }

    pair<int, int> get(int v, int l, int r, int ql, int qr) {
        if (r <= ql || qr <= l) {
            return NEUTRAL;
        }
        if (ql <= l && r <= qr) {
            return tree[v];
        }
        do_push(v);
        int m = (l + r) / 2;
        return min(get(2 * v, l, m, ql, qr), get(2 * v + 1, m, r, ql, qr));
    }
    pair<int, int> get(int ql, int qr) {
        if (ql == qr) return NEUTRAL;
        return get(1, 0, n, ql, qr);
    }
};

int n, k;
vector<int> r;
vector<int> val;
void init(i32 K, vector<i32> R) {
    n = len(R);
    r.resize(n);
    for (int i = 0; i < n; i++) {
        r[i] = R[i];
    }
    k = K;
    val.resize(n);

    SegmentTree tree(r);
    set<int> zero;
    set<pair<int, int>> q;
    auto add = [&] (int i) {
        auto it = zero.insert(i).first;
        auto it1 = it, it2 = it;
        if (it != zero.begin()) {
            it1--;
        }
        else {
            it1 = prev(zero.end());
        }
        it2++;
        if (it2 == zero.end()) {
            it2 = zero.begin();
        }
        int i1 = *it1, i2 = *it2;

        int dist = i2 - i1;
        if (dist <= 0) {
            dist += n;
        }
//            assert(q.count({dist, *it2}) == 1);
        if (!q.empty()) {
            q.erase({dist, i2});
        }
        dist = i - i1;
        if (dist <= 0) dist += n;
        q.insert({dist, i});
        dist = i2 - i;
        if (dist <= 0) dist += n;
        q.insert({dist, i2});
    };
    auto ers = [&] (int i) {
//        assert(zero.count(i) == 1);
        auto it = zero.find(i);
        auto it1 = it, it2 = it;
        if (it != zero.begin()) {
            it1--;
        }
        else {
            it1 = prev(zero.end());
        }
        it2++;
        if (it2 == zero.end()) {
            it2 = zero.begin();
        }

        int i1 = *it1, i2 = *it2;
        int dist = i - i1;
        if (dist <= 0) dist += n;
//        assert(q.count({dist, i}) == 1);
        q.erase({dist, i});
        dist = i2 - i;
        if (dist <= 0) dist += n;
//            assert(q.count({dist, *it2}) == 1);
        q.erase({dist, i2});

        if (len(zero) > 1) {
            int dist = i2 - i1;
            if (dist <= 0) {
                dist += n;
            }
            q.insert({dist, i2});
        }

        zero.erase(it);
    };

    for (int cur = n - 1; cur >= 0; cur--) {
        while (true) {
            auto res = tree.get(0, n);
            if (res.first == 0) {
                add(res.second);
                tree.modify(res.second, res.second + 1, 2 * n);
            }
            else {
                break;
            }
        }

//        assert(!q.empty());
        int mx = prev(q.end())->second;
        val[mx] = cur;
        ers(mx);

        tree.modify(max((int)(0), mx - k + 1), mx, -1);
        tree.modify(min(n, n + mx - k + 1), n, -1);
    }

//    for (int i = 0; i < n; i++) {
//        cout << val[i] << ' ';
//    }
//    cout << '\n';
}

i32 compare_plants(i32 x, i32 y) {
    if (val[x] < val[y]) return -1;
	return 1;
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25