제출 #850596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850596		LucaIlie	Garden (JOI23_garden)	C++17	45 / 100	3032 ms	5720 KiB

garden

#include <bits/stdc++.h>

using namespace std;

const int MAX_D = 5000;

struct info {
    bool all0;
    int pref0, suf0, max0;

    info operator + ( const info &x ) const {
        info ans;

        ans.all0 = all0 & x.all0;
        ans.pref0 = pref0 + all0 * x.pref0;
        ans.suf0 = x.suf0 + x.all0 * suf0;
        ans.max0 = max( max( max0, x.max0 ), suf0 + x.pref0 );

        return ans;
    }
};

struct SegTree {
    info segTree[4 * MAX_D];

    void update( int v, int l, int r, int p, int x ) {
        if ( l > p || r < p )
            return;

        if ( l == r ) {
            segTree[v] = { (x == 0), (x == 0), (x == 0), (x == 0) };
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, p, x );
        update( v * 2 + 2, mid + 1, r, p, x );
        segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
    }
};

SegTree fr;
int frecvX[MAX_D], frecvY[MAX_D], f[MAX_D];
vector<int> vx[MAX_D];

int main() {
    int n, m, d;

    cin >> n >> m >> d;
    for ( int i = 0; i < n; i++ ) {
        int x, y;
        cin >> x >> y;
        frecvX[x]++;
        frecvY[y]++;
    }
    for ( int i = 0; i < m; i++ ) {
        int x, y;
        cin >> x >> y;
        vx[x].push_back( y );
        frecvY[y]++;
    }

    int minArea = d * d;
    for ( int l = 0; l < d; l++ ) {
        for ( int i = 0; i < d; i++ ) {
            f[i] = frecvY[i];
            fr.update( 0, 0, d - 1, i, f[i] );
        }

        int countX = 0;
        for ( int r = l; r < d; r++ ) {
            countX += frecvX[r];
            for ( int y: vx[r] ) {
                f[y]--;
                fr.update( 0, 0, d - 1, y, f[y] );
            }

            int max0 = fr.segTree[0].max0;
            int pref0 = fr.segTree[0].pref0;
            int suf0 = fr.segTree[0].suf0;
            max0 = max( max0, min( d, suf0 + pref0 ) );

            if ( countX >= n )
                minArea = min( minArea,  (r - l + 1) * (d - max0) );
        }


        for ( int r = 0; r < l; r++ ) {
            countX += frecvX[r];
            for ( int y: vx[r] ) {
                f[y]--;
                fr.update( 0, 0, d - 1, y, f[y] );
            }

            int max0 = fr.segTree[0].max0;
            int pref0 = fr.segTree[0].pref0;
            int suf0 = fr.segTree[0].suf0;
            max0 = max( max0, min( d, suf0 + pref0 ) );

            if ( countX >= n )
                minArea = min( minArea,  (d - l + r + 1) * (d - max0) );
        }
    }

    cout << minArea;

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25