Submission #1197883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197883		og_matveychick1	Cultivation (JOI17_cultivation)	C++20	65 / 100	2094 ms	8804 KiB

cultivation

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

const ll N = 300;

ll n, r, c, x[N], y[N], ans = 2e9, _x[N], _y[N], ps[N], pL[N][N], pR[N][N], pmx[N][N],
        itl[N], itr[N], fL[N * N], fR[N * N], fmx[N * N], cL[N * N], cR[N * N], cmx[N * N];

void prec() {
    for (ll gl = 0; gl < n; gl++) {
        for (ll gr = gl; gr < n; gr++) {
            vector<ll> a;
            for (ll i = gl; i <= gr; i++) a.push_back(y[i]);
            sort(a.begin(), a.end());
            pL[gl][gr] = a[0];
            pR[gl][gr] = c - 1 - a[gr - gl];
            for (ll i = 1; i < a.size(); i++) pmx[gl][gr] = max(pmx[gl][gr], a[i] - a[i - 1] - 1);
            fL[gl * N + gr] = pL[gl][gr];
            fR[gl * N + gr] = pR[gl][gr];
            fmx[gl * N + gr] = pmx[gl][gr];
        }
    }
    sort(fL, fL + N * N);
    sort(fR, fR + N * N);
    sort(fmx, fmx + N * N);
    for (ll gl = 0; gl < n; gl++) {
        for (ll gr = gl; gr < n; gr++) {
            pL[gl][gr] = lower_bound(fL, fL + N * N, pL[gl][gr]) - fL;
            pR[gl][gr] = lower_bound(fR, fR + N * N, pR[gl][gr]) - fR;
            pmx[gl][gr] = lower_bound(fmx, fmx + N * N, pmx[gl][gr]) - fmx;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> r >> c >> n;
    for (ll i = 0; i < n; i++) cin >> x[i] >> y[i], x[i]--, y[i]--;
    iota(ps, ps + n, 0);
    sort(ps, ps + n, [&](ll a, ll b) { return x[a] < x[b]; });
    for (ll i = 0; i < n; i++) _x[i] = x[ps[i]], _y[i] = y[ps[i]];
    for (ll i = 0; i < n; i++) swap(x[i], _x[i]), swap(y[i], _y[i]);

    prec();
    for (ll up = 0; up < n; up++) { // n
        vll cup;
        for (ll i = 0; i < n; i++) {
            cup.push_back(r - 1 - x[i]);
            for (ll j = i; j < n; j++) {
                cup.push_back(max(0ll, abs(x[i] - x[j]) - 1 - x[up]));
            }
        }
        memset(cL, 0, sizeof cL);
        memset(cR, 0, sizeof cR);
        memset(cmx, 0, sizeof cmx);
        sort(cup.begin(), cup.end());
        cup.resize(unique(cup.begin(), cup.end()) - cup.begin());
        ll il = 0, ir = -1;
        vector<array<ll, 2>> s;
        ll iL = -1, iR = -1, imx = -1;
        ll ce = 0;
        for (ll i = 0; i < n; i++) { // n^3
            if (x[i] + cup[0] + 1 < r) {
                while (il < n && x[il] + cup[0] < x[i] + cup[0] + 1) il++;
                while (ir + 1 < n && x[ir + 1] - x[up] <= x[i] + cup[0] + 1) ir++;
                itl[i] = il;
                itr[i] = ir;
                if (ir < il) ce++;
                else {
                    iL = max(iL, pL[itl[i]][itr[i]]);
                    iR = max(iR, pR[itl[i]][itr[i]]);
                    imx = max(imx, pmx[itl[i]][itr[i]]);
                    cL[pL[itl[i]][itr[i]]]++;
                    cR[pR[itl[i]][itr[i]]]++;
                    cmx[pmx[itl[i]][itr[i]]]++;
                }
                ll pr = ir;
                while (pr + 1 < n) {
                    pr++;
                    s.push_back({(x[pr] - x[up]) - (x[i] + cup[0] + 1), i});
                }
                s.push_back({r - (x[i] + cup[0] + 1), i});
            }
        }
        il = 0, ir = -1;
        while (il < n && x[il] + cup[0] < 0) il++;
        while (ir + 1 < n && x[ir + 1] - x[up] <= 0) ir++;
        sort(s.begin(), s.end());
        ll it = 0;
        ans = min(ans, (ce ? (ll) 2e9 : max(max(fmx[pmx[il][ir]], (imx != -1 ? fmx[imx] : 0ll)),
                                             max(fL[pL[il][ir]], (iL != -1 ? fL[iL] : 0ll)) +
                                             max(fR[pR[il][ir]], (iR != -1 ? fR[iR] : 0ll)))) +
                       cup[0] + x[up]);
        for (ll dn = 1; dn < cup.size(); dn++) {
            while (it < s.size() && s[it][0] <= cup[dn]) {
                ll i = s[it][1];
                if (itr[i] < itl[i]) ce--;
                else {
                    cL[pL[itl[i]][itr[i]]]--;
                    cR[pR[itl[i]][itr[i]]]--;
                    cmx[pmx[itl[i]][itr[i]]]--;
                    while (iL >= 0 && !cL[iL]) iL--;
                    while (iR >= 0 && !cR[iR]) iR--;
                    while (imx >= 0 && !cmx[imx]) imx--;
                }
                itr[i]++;
                if (itr[i] != n) {
                    iL = max(iL, pL[itl[i]][itr[i]]);
                    iR = max(iR, pR[itl[i]][itr[i]]);
                    imx = max(imx, pmx[itl[i]][itr[i]]);
                    cL[pL[itl[i]][itr[i]]]++;
                    cR[pR[itl[i]][itr[i]]]++;
                    cmx[pmx[itl[i]][itr[i]]]++;
                }
                it++;
            }
            while (il < n && x[il] + cup[0] < 0) il++;
            while (ir + 1 < n && x[ir + 1] - x[up] <= 0) ir++;
            ans = min(ans, (ce ? (ll) 2e9 : max(max(fmx[pmx[il][ir]], (imx != -1 ? fmx[imx] : 0ll)),
                                                 max(fL[pL[il][ir]], (iL != -1 ? fL[iL] : 0ll)) +
                                                 max(fR[pR[il][ir]], (iR != -1 ? fR[iR] : 0ll)))) +
                           cup[dn] + x[up]);
        }
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 0 / 20