Submission #1259321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259321		biank	Comparing Plants (IOI20_plants)	C++20	100 / 100	1216 ms	140068 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;

const int INF = 1e9, SZ = 1 << 19;

ii operator+(const ii &a, const int b) {
    return {a.fst + b, a.snd};
} 
 
struct Node {
    ii l, ans;
    int tam, mini, r;
    Node() { ans = ii{-INF, -1}, l = ii{0, -1}, tam = r = 0, mini = INF; }
    Node(const int &val, const int &idx) { ans = l = {1, idx}, tam = 1, mini = val, r = 0; }
    friend Node merge(const Node &a, const Node &b) {
        Node c;
        c.tam = a.tam + b.tam;
        c.mini = min(a.mini, b.mini);
        c.l = a.l, c.r = b.r;
        if (a.mini == b.mini) {
            c.ans = max({a.ans, b.ans, b.l+a.r});
        } else if (a.mini < b.mini) {
            c.r = a.r + b.tam;
            c.ans = a.ans;
        } else {
            c.l = b.l + a.tam;
            c.ans = max(c.l, b.ans);
        }
        return c;
    }
};

Node st[2 * SZ];
int lazy[2 * SZ];

void pass(int u) {
    if (u < SZ) {
        lazy[2 * u] += lazy[u];
        lazy[2 * u + 1] += lazy[u];
    }
    st[u].mini += lazy[u];
    lazy[u] = 0;
}

void update(int s, int e, int v, int l = 0, int r = SZ, int u = 1) {
    pass(u);
    if (e <= l || r <= s) return;
    if (s <= l && r <= e) {
        lazy[u] = v;
        return pass(u);
    }
    int m = (l + r) / 2;
    update(s, e, v, l, m, 2 * u);
    update(s, e, v, m, r, 2 * u + 1);
    st[u] = merge(st[2 * u], st[2 * u + 1]);
}

const int MAX_N = 2e5 + 9;
const int MAX_K = 20;

int L[MAX_K][MAX_N], R[MAX_K][MAX_N];
ll distL[MAX_K][MAX_N], distR[MAX_K][MAX_N];
int N, K, h[MAX_N];

ii maxi[2 * SZ];

void updateMaxi(int p, int v) {
    maxi[p += SZ].fst = v;
    while (p /= 2) maxi[p] = max(maxi[2 * p], maxi[2 * p + 1]);
}

void chmax(ii &a, ii b) {
    if (b > a) a = b;
}

ii queryMaxi(int l, int r) {
    ii ret = {-INF, -1};
    for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
        if (l & 1) chmax(ret, maxi[l++]);
        if (r & 1) chmax(ret, maxi[--r]);
    }
    return ret;
}

void init(int k, vector <int> r) {
    const int n = sz(r);
    N = n, K = k;
    forn(i, 2 * n) st[i + SZ] = Node(r[i % n], i);
    dforsn(i, 1, SZ) st[i] = merge(st[2 * i], st[2 * i + 1]);
    vi order;
    forn(i, n) {
        auto [_, pos] = st[1].ans;
        pos %= n;
        order.pb(pos);
        if (k <= pos) {
            update(pos - k + 1, pos, -1);
        } else {
            update(0, pos, -1);
            update(2 * n + pos - k + 1, 2 * n, -1);
        }
        update(pos - k + 1 + n, pos + n, -1);
        update(pos, pos + 1, INF);
        update(pos + n, pos + n + 1, INF);
        h[pos] = n - i - 1;
    }
    reverse(all(order));
    forn(i, 2 * SZ) maxi[i] = {-INF, i - SZ};
    for (int pos : order) {
        ii bestLeft = {-INF, -1}, bestRight = {-INF, -1};
        if (k <= pos) {
            chmax(bestLeft, queryMaxi(pos - k + 1, pos));
        } else {
            chmax(bestLeft, queryMaxi(0, pos));
            chmax(bestLeft, queryMaxi(n + pos - k + 1, 2 * n));
        }
        if (pos < n - k + 1) {
            chmax(bestRight, queryMaxi(pos + 1, pos + k));
        } else {
            chmax(bestRight, queryMaxi(pos + 1, n));
            chmax(bestRight, queryMaxi(0, pos + k - n));
        }
        if (bestLeft.fst == -INF) bestLeft.snd = pos;
        if (bestRight.fst == -INF) bestRight.snd = pos;
        L[0][pos] = bestLeft.snd;
        distL[0][pos] = (pos - L[0][pos] + n) % n;
        R[0][pos] = bestRight.snd;
        distR[0][pos] = (R[0][pos] - pos + n) % n;
        updateMaxi(pos, h[pos]);
    }
    forn(p, MAX_K - 1) forn(i, n) {
        int j = L[p][i];
        L[p + 1][i] = L[p][j];
        distL[p + 1][i] = distL[p][i] + distL[p][j];
    }
    forn(p, MAX_K - 1) forn(i, n) {
        int j = R[p][i];
        R[p + 1][i] = R[p][j];
        distR[p + 1][i] = distR[p][i] + distR[p][j];
    }
}

bool reacheableLeft(int x, int y) {
    ll currDist = (x - y + N) % N;
    dforn(i, MAX_K) {
        if (currDist >= distL[i][x]) {
            currDist -= distL[i][x];
            x = L[i][x];
        }
    }
    return currDist < K && h[x] >= h[y];
}

bool reacheableRight(int x, int y) {
    ll currDist = (y - x + N) % N;
    dforn(i, MAX_K) {
        if (currDist >= distR[i][x]) {
            currDist -= distR[i][x];
            x = R[i][x];
        }
    }
    return currDist < K && h[x] >= h[y]; 
}

bool reacheable(int x, int y) {
    return reacheableLeft(x, y) || reacheableRight(x, y);
}

int compare_plants(int x, int y) {
    if (reacheable(x, y)) return 1;
    if (reacheable(y, x)) return -1;
    return 0;
}

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