Submission #836024

#	Time	Username	Problem	Language	Result	Execution time	Memory
836024		maomao90	Comparing Plants (IOI20_plants)	C++17	49 / 100	2011 ms	35144 KiB

plants

// I can do all things through Christ who strengthens me
// Philippians 4:13

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < (k); i++)
#define RREP(i, j, k) for (int i = j; i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 200005;

int n, k;
vi r;
int h[MAXN], th[MAXN];

vi adj[MAXN];
bool vis[MAXN];
void dfs(int u) {
    for (int v : adj[u]) {
        if (vis[v]) {
            continue;
        }
        vis[v] = 1;
        dfs(v);
    }
}

#define MLR int mid = (lo + hi) >> 1, lc = u << 1, rc = u << 1 ^ 1
struct SegTree {
    pair<ii, int> mx[MAXN * 4];
    ii lz[MAXN * 4];
    void init(int u = 1, int lo = 0, int hi = n - 1) {
        lz[u] = {0, 0};
        if (lo == hi) {
            mx[u] = {{r[lo], 0}, lo};
            return;
        }
        MLR;
        init(lc, lo, mid);
        init(rc, mid + 1, hi);
        mx[u] = max(mx[lc], mx[rc]);
    }
    void apply(ii x, int u, int lo, int hi) {
        mx[u].FI.FI += x.FI;
        mx[u].FI.SE += x.SE;
        lz[u].FI += x.FI;
        lz[u].SE += x.SE;
    }
    void propo(int u, int lo, int hi) {
        if (lz[u] == ii(0, 0)) {
            return;
        }
        MLR;
        apply(lz[u], lc, lo, mid);
        apply(lz[u], rc, mid + 1, hi);
        lz[u] = {0, 0};
    }
    void incre(int s, int e, ii x, int u = 1, int lo = 0, int hi = n - 1) {
        if (s >= n) {
            incre(s - n, e - n, x);
            return;
        }
        if (e >= n) {
            incre(s, n - 1, x);
            incre(0, e - n, x);
            return;
        }
        if (lo >= s && hi <= e) {
            apply(x, u, lo, hi);
            return;
        }
        MLR;
        propo(u, lo, hi);
        if (s <= mid) {
            incre(s, e, x, lc, lo, mid);
        }
        if (e > mid) {
            incre(s, e, x, rc, mid + 1, hi);
        }
        mx[u] = max(mx[lc], mx[rc]);
    }
    pair<ii, int> qmx(int s, int e, int u = 1, int lo = 0, int hi = n - 1) {
        if (s >= n) {
            return qmx(s - n, e - n);
        }
        if (e >= n) {
            return max(qmx(s, n - 1), qmx(0, e - n));
        }
        if (lo >= s && hi <= e) {
            return mx[u];
        }
        MLR;
        propo(u, lo, hi);
        pair<ii, int> res = {{-INF, -INF}, -INF};
        if (s <= mid) {
            mxto(res, qmx(s, e, lc, lo, mid));
        }
        if (e > mid) {
            mxto(res, qmx(s, e, rc, mid + 1, hi));
        }
        return res;
    }
} st1, st2;

struct DSU {
    int p[MAXN], rnk[MAXN];
    void init() {
        REP (i, 0, n) {
            p[i] = i;
            rnk[i] = 0;
        }
    }
    int findp(int i) {
        if (p[i] == i) {
            return i;
        }
        return p[i] = findp(p[i]);
    }
    bool join(int a, int b) {
        int pa = findp(a), pb = findp(b);
        if (pa == pb) {
            return 0;
        }
        if (rnk[pa] < rnk[pb]) {
            swap(pa, pb);
        }
        if (rnk[pa] == rnk[pb]) {
            rnk[pa]++;
        }
        p[pb] = pa;
        return 1;
    }
} ds1, ds2;

void init(int _k, vi _r) {
    k = _k; r = _r;
    n = SZ(r);
    st1.init();
    st2.init();
    ds1.init();
    ds2.init();
    REP (i, 0, n) {
        if (r[i] == k - 1) {
            st1.incre(i + 1, i + k - 1, {0, -1});
            st2.incre(i, i, {-INF, -INF});
        }
    }
    int z = 1;
    while (1) {
        vi todo;
        while (1) {
            auto [tmp, id] = st1.qmx(0, n - 1);
            if (tmp != ii(k - 1, 0)) {
                break;
            }
            cerr << id << ' ' << z << '\n';
            h[id] = z;
            st1.incre(id, id, {-INF, -INF});
            todo.pb(id);
            if (k == 2) {
                REP (j, id + 1, id + k) {
                    if (h[j % n] == 0) {
                        ds1.join(id, j % n);
                    } else {
                        ds2.join(id, j % n);
                    }
                }
            }
            if (k != 2 && n <= 300) {
                REP (j, id + 1, id + k) {
                    if (h[j % n] == 0) {
                        //adj[id].pb(j % n);
                        ds1.join(id, j % n);
                    }
                }
            }
        }
        if (todo.empty()) {
            break;
        }
        for (int id : todo) {
            st1.incre(id + 1, id + k - 1, {0, 1});
            st1.incre(id - k + 1 + n, id - 1 + n, {1, 0});
            st2.incre(id - k + 1 + n, id - 1 + n, {1, 0});
            auto [v, u] = st2.qmx(id - k + 1 + n, id - 1 + n);
            while (v.FI == k - 1) {
                st1.incre(u + 1, u + k - 1, {0, -1});
                st2.incre(u, u, {-INF, -INF});
                tie(v, u) = st2.qmx(id - k + 1 + n, id - 1 + n);
            }
        }
        z++;
    }
    {
        REP (i, 0, n) {
            r[i] = k - 1 - r[i];
        }
        st1.init();
        st2.init();
        REP (i, 0, n) {
            if (r[i] == k - 1) {
                st1.incre(i + 1, i + k - 1, {0, -1});
                st2.incre(i, i, {-INF, -INF});
            }
        }
        int z = 1;
        while (1) {
            vi todo;
            while (1) {
                auto [tmp, id] = st1.qmx(0, n - 1);
                if (tmp != ii(k - 1, 0)) {
                    break;
                }
                cerr << id << ' ' << z << '\n';
                th[id] = z;
                st1.incre(id, id, {-INF, -INF});
                todo.pb(id);
                if (k != 2 && n <= 300) {
                    REP (j, id + 1, id + k) {
                        if (th[j % n] == 0) {
                            //adj[id].pb(j % n);
                            ds2.join(id, j % n);
                        }
                    }
                }
            }
            if (todo.empty()) {
                break;
            }
            for (int id : todo) {
                st1.incre(id + 1, id + k - 1, {0, 1});
                st1.incre(id - k + 1 + n, id - 1 + n, {1, 0});
                st2.incre(id - k + 1 + n, id - 1 + n, {1, 0});
                auto [v, u] = st2.qmx(id - k + 1 + n, id - 1 + n);
                while (v.FI == k - 1) {
                    st1.incre(u + 1, u + k - 1, {0, -1});
                    st2.incre(u, u, {-INF, -INF});
                    tie(v, u) = st2.qmx(id - k + 1 + n, id - 1 + n);
                }
            }
            z++;
        }
    }
	return;
}

int compare_plants(int x, int y) {
    /*
    if (n <= 300) {
        REP (i, 0, n) {
            vis[i] = 0;
        }
        vis[x] = 1;
        dfs(x);
        if (vis[y]) {
            return -1;
        }
        REP (i, 0, n) {
            vis[i] = 0;
        }
        vis[y] = 1;
        dfs(y);
        if (vis[x]) {
            return 1;
        }
        return 0;
    }
    */
    if (k == 2 || n <= 300) {
        if (ds1.findp(x) != ds1.findp(y) && ds2.findp(x) != ds2.findp(y)) {
            return 0;
        }
        if (ds1.findp(x) == ds1.findp(y)) {
            if (h[x] > h[y]) {
                return 1;
            } else {
                return -1;
            }
        } else {
            if (th[x] > th[y]) {
                return -1;
            } else {
                return 1;
            }
        }
    } 
    if (h[x] > h[y]) {
        return 1;
    } else {
        return -1;
    }
}

• Subtask 1: 5 / 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