Submission #1122693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122693		ksujay2	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	3537 ms	7488 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; 
vector<int> a, b, c, o;

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;

}

int mult = 1;
bool fl = false;

int check(int x, vector<int>& b) {
    int mx = 0;
    int j = 0;
    for(int i : o) {
        if((x <= i && i < x + N) || (x - 2 * N <= i && i < x - N)) {
            mx = max(mult * (a[i] - b[j]), mx);
            j++;
        }
    }
    return mx;
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> N;
    a.resize(2 * 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.begin(), a.begin() + k, a.end());

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

    b.resize(N);
    c.resize(N);
    for(int i = 0; i < N; i++) cin >> b[i];
    for(int i = 0; i < N; i++) cin >> c[i];
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());

    auto find_range = [&] (int o, int y, vector<int>& b) {
        fl = !fl;
        int l = ((check(o, b) <= y) == !fl) + fl - 1;
        fl = !fl;
        int r = bsmax(0, N, [&] (int x) {
            return ((check(o + x, b) <= y) == !fl);
        }) + fl;
        return make_pair(l, r);
    };

    auto check = [&] (int x) {

        mult = 1;
        fl = false;
        auto [l1, r1] = find_range(0, x, b);
        auto [l5, r5] = find_range(0, x, c);
        fl = true;
        auto [l3, r3] = find_range(N, x, c);
        auto [l7, r7] = find_range(N, x, b);

        mult = -1;
        fl = true;
        auto [l4, r4] = find_range(0, x, b);
        auto [l8, r8] = find_range(0, x, c);
        fl = false;
        auto [l2, r2] = find_range(N, x, c);
        auto [l6, r6] = find_range(N, x, b);

        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: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33