Submission #1062771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062771		vjudge1	Comparing Plants (IOI20_plants)	C++17	0 / 100	34 ms	3320 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];
    }
    
    ii query(int l, int r, int u, int s, int d) {
        int mij = (s + d) >> 1;
        if(l <= s && d <= r) return V[u];
        if(r <= mij) return query(l, r, u << 1, s, mij);
        if(l > mij) return query(l, r, u << 1 | 1, mij + 1, d);
        return min(query(l, r, u << 1, s, mij), query(l, r, u << 1 | 1, mij + 1, d));
    }
    

    ii query(int l, int r) {
        if(l < 0 && r < 0) {
            l += n;
            r += n;
        }
        if(r >= n && l >= n) {
            l -= n;
            r -= n;
        }

        if(l >= 0 && r < n) return query(l, r, 1, 0, n - 1);
        if(l < 0 && r >= n) return query(0, n - 1, 1, 0, n - 1);
        if(l < 0) {
            return min(query(0, r, 1, 0, n - 1), query(l + n, n - 1, 1, 0, n - 1));
        }
        if(r >= n) {
            return min(query(l, n - 1, 1, 0, n - 1), query(0, r - n, 1, 0, n - 1));
        }
    }
};

const int INF = 1e9;

vi Perm;

vi stanga, dreapta;
int n, k;
void init(int k, vi r) {
    ::k = k;
    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);
    vi ord;
    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;
        ord.push_back(u);
    }
    AINT A2(n);
    for(int i = 0; i < n; ++i)
        A2.update(i, {-Perm[i], i});
    stanga.resize(2 * n, -1);
    dreapta.resize(2 * n, -1);
    for(auto it : ord) {
        A2.update(it, it, INF);// dezactivam
        auto [v1, p1] = A2.query(it - k + 1, it - 1);
        if(v1 <= 0) {
            if(p1 > n) {
                p1 -= n;
            }
            stanga[it] = p1;
            stanga[it + n] = p1 + n;
        }
        auto [v2, p2] = A2.query(it + 1, it + k - 1);
        if(v2 <= 0) {
            if(p2 < it) p2 += n;
            dreapta[it] = p2;
            dreapta[it + n] = p2 + n;
        }
    }
}

bool comparable_dr(int x, int y) {
    if(Perm[x] < Perm[y]) {
        swap(x, y);
    }
    if(y < x)
        y += n;
    while(x < y) {
        if(dreapta[x] == -1) {
            return false;
        }
        if(dreapta[x] < y) {
            x = dreapta[x];
            if(Perm[x % n] < Perm[y % n]) return false;
            continue;
        }
        return true;
    }
    return true;
}

bool comparable_st(int x, int y) {
    if(Perm[x] < Perm[y]) {
        swap(x, y);
    }
    if(y > x)
        x += n;
    //acum y < x
    while(x > y) {
        if(stanga[x] < 0) {
            return false;
        }
        if(stanga[x] > y) {
            x = stanga[x];
            if(Perm[x % n] < Perm[y % n]) return false;
            continue;
        }
        return true;
    }
    return true;
}

bool comparable(int x, int y) {
    return comparable_st(x, y) || comparable_dr(x, y);
}

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

Compilation message (stderr)

plants.cpp: In member function 'ii AINT::query(int, int)':
plants.cpp:86:5: warning: control reaches end of non-void function [-Wreturn-type]
   86 |     }
      |     ^

• 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