Submission #850610

#	Time	Username	Problem	Language	Result	Execution time	Memory
850610		LucaIlie	Garden (JOI23_garden)	C++17	0 / 100	263 ms	856 KiB

garden

#include <bits/stdc++.h>

using namespace std;

const int MAX_D = 5000;

int frecvX[MAX_D], frecvY[MAX_D], posY[MAX_D], leftt[MAX_D], rightt[MAX_D], f[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++ ) {
            f[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 max0 = 0;
        for ( int i = 0; i < d; ) {
            int j = i;
            while ( j < d && f[i] == f[j] )
                j++;
            j--;
            leftt[i] = leftt[j] = i;
            rightt[i] = rightt[j] = j;
            if ( f[i] == 0 )
                max0 = max( max0, j - i + 1 );
            i = j + 1;
        }

        int countX = 0;
        int lat = 0;
        int r = l;
        do {
            lat++;
            countX += frecvX[r];
            for ( int y: upd[r] ) {
                f[y] = 0;
                if ( y > 0 && f[y - 1] == 0 ) {
                    leftt[y] = leftt[y - 1];
                    rightt[y] = rightt[y - 1] = rightt[leftt[y - 1]] = y;
                    max0 = max( max0, rightt[y] - leftt[y] + 1 );
                }
                if ( y < d - 1 && f[y + 1] == 0 ) {
                    rightt[y] = rightt[y + 1];
                    leftt[y] = leftt[y + 1] = leftt[rightt[y + 1]] = y;
                    max0 = max( max0, rightt[y] - leftt[y] + 1 );
                }
            }

            int pref0 = (f[0] == 0 ? rightt[0] + 1 : 0);
            int suf0 = (f[d - 1] == 0 ? d - leftt[d - 1] : 0);
            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;
}

Compilation message (stderr)

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