Submission #1204884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204884		LucaIlie	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	4 / 100	5097 ms	50088 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct AINT {
    int ls, rs;
    vector<int> aint, lazy;

    void init(int l, int r) {
        aint.clear();
        lazy.clear();
        aint.resize(4 * (r - l + 1));
        lazy.resize(4 * (r - l + 1));
        ls = l;
        rs = r;
    }   

    void propag(int v, int l, int r) {
        aint[v] += lazy[v];
        if (l != r) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void update(int v, int l, int r, int lu, int ru, int x) {
        propag(v, l, r);

        if (l > ru || r < lu)
            return;

        if (lu <= l && r <= ru) {
            // printf("NU %d %d %d\n", l, r, x);
            lazy[v] += x;
            propag(v, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(v * 2 + 1, l, mid, lu, ru, x);
        update(v * 2 + 2, mid + 1, r, lu, ru, x);
        aint[v] = min(aint[v * 2 + 1], aint[v * 2 + 2]);
    }

    void update(int l, int r, int x) {
        update(0, ls, rs, l, r, x); 
    }

    int query(int v, int l, int r, int lq, int rq) {
        if (l > rq || r < lq)
            return (int)1e9;

        if (lq <= l && r <= rq)
            return aint[v];

        int mid = (l + r) / 2;
        return min(query(v * 2 + 1, l, mid, lq, rq), query(v * 2 + 2, mid + 1, r, lq, rq));
    }

    int query(int l, int r) {
        return query(0, ls, rs, l, r);
    }
};

const int MAX_N = 3e5;
const int MAX_VAL = 1e9;
int n;
int a[2 * MAX_N + 1], b[MAX_N + 1], c[MAX_N + 1];
int leftPos[2 * MAX_N + 1], rightPos[2 * MAX_N + 1];
int greaterInOtherSide[2 * MAX_N + 1];
bool startB[2 * MAX_N + 1], startC[2 * MAX_N + 1];
AINT rp, pl;

bool checkMatch() {
    bool isMatch = false;
    for (int s = 1; s <= 2 * n; s++) {
        int t = s + n;
        if (t > 2 * n)
            t -= 2 * n;
        // printf("%d %d %d %d\n", s, t, startB[s], startC[t]);
        isMatch |= (startB[s] & startC[t]);
        
    }
    // printf("%d\n", isMatch);
    return isMatch;
}

void updatePos(int i, int p) {
    // printf("updare pos %d %d\n", i, p);
    rp.update(i, i, rightPos[i] - p);
    pl.update(i, i, p - leftPos[i]);
}

void updateRangePos(int l, int r, int x) {
    if (l > r)
        return;
    // printf("updare range pos %d %d %d\n", l, r, x);
    rp.update(l, r, -x);
    pl.update(l, r, +x);
}

void checkPositionsForColor(int d, int b[], bool start[]) {
    // printf("FAC %d\n", d);
    int j;
    j = 0;
    for (int i = 1; i <= n; i++) {
        while (j + 1 <= n && b[j + 1] <= a[i] + d)
            j++;
        rightPos[i] = j;
    }
    j = 0;
    for (int i = 2 * n; i >= n + 1; i--) {
        while (j + 1 <= n && b[j + 1] <= a[i] + d)
            j++;
        rightPos[i] = j;
    }

    j = 1;
    for (int i = 1; i <= n; i++) {
        while (j <= n && b[j] < a[i] - d)
            j++;
        leftPos[i] = j;
    }
    j = 1;
    for (int i = 2 * n; i >= n + 1; i--) {
        while (j <= n && b[j] < a[i] - d)
            j++;
        leftPos[i] = j;
    }

    j = n + 1;
    for (int i = n; i >= 1; i--) {
        while (j + 1 <= 2 * n && a[j + 1] >= a[i])
            j++;
        greaterInOtherSide[i] = j;
    }

    j = n + 1;
    for (int i = n + 1; i <= 2 * n; i++) {
        while (j - 1 >= 1 && a[j - 1] > a[i])
            j--;
        greaterInOtherSide[i] = j;
    }

    // for (int i = 1; i <= 2 * n; i++)
        // printf("%d %d %d\n", leftPos[i], rightPos[i], greaterInOtherSide[i]);
    // printf("\n");

    rp.init(1, 2 * n);
    pl.init(1, 2 * n);
    for (int i = 1; i <= n; i++) 
        updatePos(i, i);
    for (int s = 1; s <= n; s++) {
        start[s] = (rp.query(s, s + n - 1) >= 0 && pl.query(s, s + n - 1) >= 0);
        int t = s + n;
        updateRangePos(s + 1, min(t - 1, greaterInOtherSide[s]), -1);
        updatePos(t, max(1, greaterInOtherSide[t] - s));
        updateRangePos(max(s + 1, greaterInOtherSide[t]), t - 1, +1);
    }
    start[n + 1] = (rp.query(n + 1, 2 * n) >= 0 && pl.query(n + 1, 2 * n) >= 0);

    rp.init(1, 2 * n);
    pl.init(1, 2 * n);
    for (int i = n + 1; i <= 2 * n; i++) 
        updatePos(i, 2 * n - i + 1);
    for (int s = n + 2; s <= 2 * n; s++) {
        int t = s - n - 1;
        
        updateRangePos(greaterInOtherSide[s - 1], t - 1, -1); 
        int pos = t;
        for (int i = s; i <= 2 * n; i++)
            pos += (a[i] < a[t]);
        updatePos(t, pos);
        //updatePos(t, t + 2 * n - max(s - 1, greaterInOtherSide[t]));
        updateRangePos(s, greaterInOtherSide[t], +1);

        start[s] = (rp.query(s, 2 * n) >= 0 && rp.query(1, t) >= 0 && pl.query(1, t) >= 0 && pl.query(s, 2 * n) >= 0);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= 2 * n; i++)
        cin >> a[i];
    b[0] = -MAX_VAL;
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    sort(b + 1, b + 1 + n);
    c[0] = -MAX_VAL;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    sort(c + 1, c + 1 + n);

    int l = -1, r = MAX_VAL;
    while (r - l > 1) {
        int d = (l + r) / 2;

        checkPositionsForColor(d, b, startB);
        checkPositionsForColor(d, c, startC);
        if (checkMatch())
            r = d;
        else
            l = d;
    }
    
    cout << r << "\n";

    return 0;
}

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