LG P5244 [USACO19FEB] Mowing Mischief P

\(\text{Code}\)

#include <bits/stdc++.h>

#define IN inline

#define eb emplace_back

using namespace std;

template<typename Tp>

IN void read(Tp &x) {

    x = 0; char ch = getchar(); int f = 0;

    for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());

    for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());

    if (f) x = ~x + 1;

}

typedef long long LL;

const int N = 2e5 + 5, M = 1e6 + 5;

const LL INF = 1e18;

struct point{int x, y;}a[N];

int lis[N], n, m;

LL f[N], g[N];

vector<int> G[N];

IN LL calc(int x1, int y1, int x0, int y0){return (LL)(x1 - x0) * (y1 - y0);}

struct SegmentTree {

    #define ls (p << 1)

    #define rs (ls | 1)

    vector<int> Q[N << 2];

    void build(int p, int l, int r) {

        Q[p].clear(); if (l == r) return;

        int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r);

    }

    void insert(int p, int l, int r, int x, int y, int z) {

        if (x > r || y < l) return;

        if (x <= l && r <= y) return Q[p].eb(z), void();

        int mid = l + r >> 1;

        insert(ls, l, mid, x, y, z), insert(rs, mid + 1, r, x, y, z);

    }

    void solve(int p, int l, int r, int L, int R, int cur) {

        if (r < l || R < L) return;

        int mid = l + r >> 1, bst = 0;

        for(int i = L; i <= R; i++) {

            LL s = f[G[cur - 1][i]] + calc(a[Q[p][mid]].x, a[Q[p][mid]].y, a[G[cur - 1][i]].x, a[G[cur - 1][i]].y);

            if (g[Q[p][mid]] > s) g[Q[p][mid]] = s, bst = i;

        }

        solve(p, l, mid - 1, bst, R, cur), solve(p, mid + 1, r, L, bst, cur);

    }

    void dfs(int p, int l, int r, int cur) {

        for(auto v : Q[p]) g[v] = INF;

        solve(p, 0, Q[p].size() - 1, l, r, cur);

        for(auto v : Q[p]) f[v] = min(f[v], g[v]);

        if (l == r) return; int mid = l + r >> 1;

        dfs(ls, l, mid, cur), dfs(rs, mid + 1, r, cur);

    }

}T;

struct BIT {

    int c[M];

    IN int lowbit(int x){return x & -x;}

    IN void add(int x, int v){for(; x <= m; x += lowbit(x)) c[x] = max(c[x], v);}

    IN int query(int x){int s = 0; for(; x; x -= lowbit(x)) s = max(c[x], s); return s;}

}bit;

IN void solve() {

    for(int i = 1; i <= n; i++) lis[i] = bit.query(a[i].y) + 1, bit.add(a[i].y, lis[i]);

    for(int i = 0; i <= n; i++) G[lis[i]].eb(i);

    for(int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end(), [](int x, int y){return a[x].x < a[y].x;});

    for(int i = 1; i <= n; i++) f[i] = INF;

    for(int i = 1; i <= n && G[i].size(); i++) {

        T.build(1, 0, G[i - 1].size() - 1);

        int p = 0, q = 0;

        for(auto j : G[i]) {

            while (p < G[i - 1].size() && a[G[i - 1][p]].x <= a[j].x) ++p;

            while (q < G[i - 1].size() && a[G[i - 1][q]].y > a[j].y) ++q;

            T.insert(1, 0, G[i - 1].size() - 1, q, p - 1, j);

        }

        T.dfs(1, 0, G[i - 1].size() - 1, i);

    }

}

int main() {

    freopen("mowing.in", "r", stdin);

    freopen("mowing.out", "w", stdout);

    read(n), read(m);

    for(int i = 1; i <= n; i++) read(a[i].x), read(a[i].y);

    sort(a + 1, a + n + 1, [](point a, point b){return a.x < b.x;});

    solve();

    int mx = 0;

    for(int i = 1; i <= n; i++) mx = max(mx, lis[i]);

    LL ans = INF;

    for(int i = 1; i <= n; i++) if (lis[i] == mx) ans = min(ans, f[i] + calc(m, m, a[i].x, a[i].y));

    printf("%lld\n", ans);

}
巴特西

LG P5244 [USACO19FEB] Mowing Mischief P

\(\text{Code}\)

最新文章

热门文章
