Submission #1122705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122705		ksujay2	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	3547 ms	9388 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
const int MXN = 300000;

int N; 
int a[2 * MXN], o[2 * MXN], b[2][MXN];

int bsmax(int lo, int hi, function<bool(int)> f)
{
    lo--;
    while (hi > lo)
    {
        int mid = (hi + lo + 1) / 2;
        if (f(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;

}

bool done[2 * MXN][2];
int sb[2 * MXN][2][2];

void sub(int x, int bc) {
    if(done[x][bc]) {
        return;
    }
    int j = 0;
    for(int i = 0; i < 2 * N; i++) {
        if((x <= o[i] && o[i] < x + N) || (x - 2 * N <= o[i] && o[i] < x - N)) {
            sb[x][bc][0] = max(-a[o[i]] + b[bc][j], sb[x][bc][0]);
            sb[x][bc][1] = max(a[o[i]] - b[bc][j], sb[x][bc][1]);
            j++;
        }
    }
    done[x][bc] = true;
};

pair<int, int> find_range (int o, int y, int bc, int fl, int gr) {
    sub(o, bc);
    int l = ((sb[o][bc][gr] <= y) == fl) + (!fl) - 1;
    int r = bsmax(0, N, [&] (int x) {
        sub(o + x, bc);
        return ((sb[o + x][bc][gr] <= y) == !fl);
    }) + fl;
    return make_pair(l, r);
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> N;
    for(int i = 0; i < 2 * N; i++) cin >> a[i];

    int k = 0;
    while(k < N && a[k] <= a[k + N]) k++;
    rotate(a, a + k, a + 2 * N);

    for(int i = 0; i < 2 * N; i++) o[i] = i;
    sort(o, o + 2 * N, [&] (int x, int y) { return a[x] < a[y]; });

    for(int bc : {0, 1}) {
        for(int i = 0; i < N; i++) cin >> b[bc][i];
        sort(b[bc], b[bc] + N);
    }

    auto check = [&] (int x) {

        auto [l1, r1] = find_range(0, x, 0, 0, 0);
        auto [l5, r5] = find_range(0, x, 1, 0, 0);
        auto [l3, r3] = find_range(N, x, 1, 1, 0);
        auto [l7, r7] = find_range(N, x, 0, 1, 0);

        auto [l4, r4] = find_range(0, x, 0, 1, 1);
        auto [l8, r8] = find_range(0, x, 1, 1, 1);
        auto [l2, r2] = find_range(N, x, 1, 0, 1);
        auto [l6, r6] = find_range(N, x, 0, 0, 1);

        bool good = false;
        {
            int l = max(l1, l2), r = min(r1, r2);
            int rl = min(l3, l4), rr = max(r3, r4);
            good = good || ((l <= r) && ((l <= rl) || (rr <= r)));
        }
        {
            int l = max(l5, l6), r = min(r5, r6);
            int rl = min(l7, l8), rr = max(r7, r8);
            good = good || ((l <= r) && ((l <= rl) || (rr <= r)));
        }
        return good;
    };

    int ans = bsmax(0, 1e9, [&] (int x) {
        return !check(x);
    }) + 1;
    cout << ans << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 37 / 37
• Subtask 5: 33 / 33