oj.uz

Submission #836021

# Submission time Handle Problem Language Result Execution time Memory
836021 2023-08-24T05:06:22 Z maomao90 Comparing Plants (IOI20_plants) C++17
60 / 100
 3668 ms 34452 KB 
// 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];

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 (n <= 300) {
                REP (j, id + 1, id + k) {
                    if (h[j % n] == 0) {
                        adj[id].pb(j % n);
                        //ds1.join(id, j % n);
                    } else {
                        adj[j % n].pb(id);
                        //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 && ds1.findp(x) != ds1.findp(y) && ds2.findp(x) != ds2.findp(y)) {
        return 0;
    } else if (h[x] > h[y]) {
        return 1;
    } else {
        return -1;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 49 ms 7880 KB Output is correct
7 Correct 89 ms 10972 KB Output is correct
8 Correct 435 ms 34372 KB Output is correct
9 Correct 441 ms 34184 KB Output is correct
10 Correct 421 ms 34144 KB Output is correct
11 Correct 363 ms 34296 KB Output is correct
12 Correct 550 ms 34344 KB Output is correct
13 Correct 356 ms 34424 KB Output is correct
14 Correct 313 ms 34400 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 56 ms 8688 KB Output is correct
8 Correct 40 ms 5160 KB Output is correct
9 Correct 6 ms 5204 KB Output is correct
10 Correct 59 ms 8656 KB Output is correct
11 Correct 49 ms 8524 KB Output is correct
12 Correct 50 ms 8780 KB Output is correct
13 Correct 54 ms 8668 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 56 ms 8688 KB Output is correct
8 Correct 40 ms 5160 KB Output is correct
9 Correct 6 ms 5204 KB Output is correct
10 Correct 59 ms 8656 KB Output is correct
11 Correct 49 ms 8524 KB Output is correct
12 Correct 50 ms 8780 KB Output is correct
13 Correct 54 ms 8668 KB Output is correct
14 Correct 110 ms 10976 KB Output is correct
15 Correct 996 ms 34256 KB Output is correct
16 Correct 109 ms 11020 KB Output is correct
17 Correct 1000 ms 34252 KB Output is correct
18 Correct 597 ms 34196 KB Output is correct
19 Correct 576 ms 34124 KB Output is correct
20 Correct 844 ms 34248 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 2 ms 5012 KB Output is correct
3 Correct 44 ms 8012 KB Output is correct
4 Correct 435 ms 34192 KB Output is correct
5 Correct 616 ms 34168 KB Output is correct
6 Correct 831 ms 34164 KB Output is correct
7 Correct 955 ms 34164 KB Output is correct
8 Correct 1010 ms 34252 KB Output is correct
9 Correct 577 ms 34204 KB Output is correct
10 Correct 522 ms 34140 KB Output is correct
11 Correct 353 ms 34076 KB Output is correct
12 Correct 409 ms 34380 KB Output is correct
13 Correct 607 ms 34452 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 6 ms 5076 KB Output is correct
7 Correct 48 ms 5708 KB Output is correct
8 Correct 1185 ms 5836 KB Output is correct
9 Correct 126 ms 5636 KB Output is correct
10 Correct 1103 ms 5836 KB Output is correct
11 Correct 53 ms 5708 KB Output is correct
12 Correct 165 ms 5708 KB Output is correct
13 Correct 3668 ms 6148 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4960 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Incorrect 4 ms 5076 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 49 ms 7880 KB Output is correct
7 Correct 89 ms 10972 KB Output is correct
8 Correct 435 ms 34372 KB Output is correct
9 Correct 441 ms 34184 KB Output is correct
10 Correct 421 ms 34144 KB Output is correct
11 Correct 363 ms 34296 KB Output is correct
12 Correct 550 ms 34344 KB Output is correct
13 Correct 356 ms 34424 KB Output is correct
14 Correct 313 ms 34400 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 6 ms 5076 KB Output is correct
20 Correct 5 ms 5204 KB Output is correct
21 Correct 56 ms 8688 KB Output is correct
22 Correct 40 ms 5160 KB Output is correct
23 Correct 6 ms 5204 KB Output is correct
24 Correct 59 ms 8656 KB Output is correct
25 Correct 49 ms 8524 KB Output is correct
26 Correct 50 ms 8780 KB Output is correct
27 Correct 54 ms 8668 KB Output is correct
28 Correct 110 ms 10976 KB Output is correct
29 Correct 996 ms 34256 KB Output is correct
30 Correct 109 ms 11020 KB Output is correct
31 Correct 1000 ms 34252 KB Output is correct
32 Correct 597 ms 34196 KB Output is correct
33 Correct 576 ms 34124 KB Output is correct
34 Correct 844 ms 34248 KB Output is correct
35 Correct 4 ms 4948 KB Output is correct
36 Correct 2 ms 5012 KB Output is correct
37 Correct 44 ms 8012 KB Output is correct
38 Correct 435 ms 34192 KB Output is correct
39 Correct 616 ms 34168 KB Output is correct
40 Correct 831 ms 34164 KB Output is correct
41 Correct 955 ms 34164 KB Output is correct
42 Correct 1010 ms 34252 KB Output is correct
43 Correct 577 ms 34204 KB Output is correct
44 Correct 522 ms 34140 KB Output is correct
45 Correct 353 ms 34076 KB Output is correct
46 Correct 409 ms 34380 KB Output is correct
47 Correct 607 ms 34452 KB Output is correct
48 Correct 2 ms 4948 KB Output is correct
49 Correct 2 ms 4948 KB Output is correct
50 Correct 2 ms 4948 KB Output is correct
51 Correct 2 ms 4948 KB Output is correct
52 Correct 3 ms 4948 KB Output is correct
53 Correct 6 ms 5076 KB Output is correct
54 Correct 48 ms 5708 KB Output is correct
55 Correct 1185 ms 5836 KB Output is correct
56 Correct 126 ms 5636 KB Output is correct
57 Correct 1103 ms 5836 KB Output is correct
58 Correct 53 ms 5708 KB Output is correct
59 Correct 165 ms 5708 KB Output is correct
60 Correct 3668 ms 6148 KB Output is correct
61 Incorrect 46 ms 9804 KB Output isn't correct
62 Halted 0 ms 0 KB -