제출 #850600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850600		LucaIlie	Garden (JOI23_garden)	C++17	0 / 100	460 ms	904 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], posY[MAX_D];
vector<int> vx[MAX_D], vy[MAX_D], upd[MAX_D];

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

    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 );
        vy[y].push_back( x );
        frecvY[y]++;
    }

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

            if ( vy[i].empty() )
                continue;
            while ( posY[i] < vy[i].size() && vy[i][posY[i]] < l )
                posY[i]++;
            posY[i] = (posY[i] - 1 + vy[i].size()) % vy[i].size();
            upd[vy[i][posY[i]]].push_back( i );
        }

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

            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;
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'int main()':
garden.cpp:77:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             while ( posY[i] < vy[i].size() && vy[i][posY[i]] < l )
      |                     ~~~~~~~~^~~~~~~~~~~~~~

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