Submission #1201918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201918		Triseedot	Comparing Plants (IOI20_plants)	C++20	14 / 100	4094 ms	20292 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()

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) {
        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) {
        return get(1, 0, n, ql, qr);
    }
};

int n, k;
vector<int> r;
vector<int> val;
void init(int K, vector<int> R) {
    r = R;
    k = K;
    n = len(r);
    val.resize(n);

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

        vector<int> idx(all(zero));
        int mx = 0;
        for (int i = 0; i < len(idx); i++) {
            int dist;
            if (i == 0) {
                dist = idx[i] + n - idx.back();
            }
            else {
                dist = idx[i] - idx[i - 1];
            }
            if (dist >= k) {
                mx = idx[i];
                break;
            }
        }
        val[mx] = cur;
        zero.erase(mx);

        tree.modify(max(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';
}

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

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