Submission #1061938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061938		vjudge1	Comparing Plants (IOI20_plants)	C++17	0 / 100	32 ms	3408 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

struct AINT {
    int n;
    vector<ii> V;
    vi Lz;

    AINT() {}
    AINT(int N) : n(N), V(4 * N, ii{0, 0}), Lz(4 * N, 0) {}

    void prop(int u, int s, int d) {
        if(!Lz[u]) return;
        V[u].first += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void update(int p, ii v, int u, int s, int d) {
        prop(u, s, d);
        if(d < p || p < s) return;
        if(s == d) {
            V[u] = v;
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = min(V[u << 1], V[u << 1 | 1]);
    }

    void update(int p, ii v) { update(p, v, 1, 0, n - 1); }
    void update(int l, int r, int v, int u, int s, int d) {
        prop(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            Lz[u] += v;
            prop(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = min(V[u << 1], V[u << 1 | 1]);
    }
    void update(int l, int r, int v) { update(l, r, v, 1, 0, n - 1); }

    ii query() {
        return V[1];
    }
};

const int INF = 1e9;

vi Perm;

void init(int k, vi r) {
    int n = int(r.size());
    vi active(n, 1);
    AINT Sol(n);
    for(int i = 0; i < n; ++i) {
        Sol.update(i, {r[i], i});
    }
    set<int> Zero, ZeroActiv;
    while(!Sol.query().first) {
        int p = Sol.query().second;
        Zero.insert(p);
        Sol.update(p, {INF, p});
    }
    auto get_urm = [&](int p) {
        auto it = Zero.upper_bound(p);
        if(it == Zero.end()) return *Zero.begin();
        return *it;
    };
    auto get_prev = [&](int p) {
        auto it = Zero.lower_bound(p);
        if(it == Zero.begin()) return *Zero.rbegin();
        --it;
        return *it;
    };
    auto dist = [&](int a, int b) {
        //!!! distanta directionata
        if(a < b) return b - a;
        return b + n - a - 1;
    };
    for(auto it : Zero) {
        int u = get_prev(it);
        if(it == u || dist(it, u) >= k)
            ZeroActiv.insert(it);
    }

    auto erase = [&](int u) {
        int urm = get_urm(u);
        ZeroActiv.erase(u);
        Zero.erase(u);
        if(urm != u) {
            int nou_pr = get_prev(urm);
            if(nou_pr == urm || dist(nou_pr, urm) >= k) {
                ZeroActiv.insert(urm);
            }
        }
    };

    auto insert = [&](int u) {
        Zero.insert(u);
        int urm = get_urm(u);
        if(urm == u) { 
            ZeroActiv.insert(u);
            return;
        }
        if(dist(u, urm) < k) {
            ZeroActiv.erase(urm);
        }
        int ant = get_prev(u);
        if(dist(ant, u) >= k)
            ZeroActiv.insert(u);
    };

    Perm.resize(n);
    for(int nr = 0; nr < n; ++nr) {
        int u = *ZeroActiv.begin();
        erase(u);
        int l = u - k + 1;
        if(l < 0) {
            Sol.update(0, u, -1);
            l = n + l;
            Sol.update(l, n - 1, -1);
        } else {
            Sol.update(l, u, -1);
        }
        while(Sol.query().first == 0) {
            int p = Sol.query().second; /// a fost popit
            insert(p);
            Sol.update(p, ii{INF, p});
        }
        Perm[u] = n - nr - 1;
    }
}


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

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