제출 #850608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850608		LucaIlie	Garden (JOI23_garden)	C++17	45 / 100	3043 ms	1152 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], posY[MAX_D];
vector<int> 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;
        vy[y].push_back( x );
    }


    for ( int y = 0; y < d; y++ )
        sort( vy[y].begin(), vy[y].end() );

    int minArea = d * d;
    for ( int l = 0; l < d; l++ ) {
        for ( int x = 0; x < d; x++ )
            upd[x].clear();
        for ( int y = 0; y < d; y++ )
            posY[y] = 0;
        for ( int y = 0; y < d; y++ ) {
            fr.update( 0, 0, d - 1, y, (frecvY[y] + vy[y].size() > 0) );

            if ( vy[y].empty() || frecvY[y] > 0 )
                continue;

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

        int countX = 0;
        int lat = 0;
        int r = l;
        do {
            lat++;
            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,  lat * (d - max0) );
            r = (r + 1) % d;
        } while ( r != l );
    }

    cout << minArea;

    return 0;
}

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

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

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