Submission #850673

#	Time	Username	Problem	Language	Result	Execution time	Memory
850673		LucaIlie	Garden (JOI23_garden)	C++17	100 / 100	1836 ms	118504 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 );

    //ifstream cin( ".in" );

    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] = 1;

            if ( frecvY[y] > 0 )
                continue;

            if ( vy[y].empty() ) {
                upd[l].push_back( y );
                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;
        int countX = 0;
        for ( int i = 0; i < d; i++ ) {
            int r = (l + i) % d;

            countX += frecvX[r];
            for ( int y: upd[r] ) {
                f[y] = 0;
                leftt[y] = rightt[y] = y;
                if ( y > 0 && f[y - 1] == 0 ) {
                    leftt[rightt[y]] = leftt[y] = leftt[y - 1];
                    rightt[y - 1] = rightt[leftt[y - 1]] = rightt[y];
                }
                if ( y < d - 1 && f[y + 1] == 0 ) {
                    rightt[leftt[y]] = rightt[y] = rightt[y + 1];
                    leftt[y + 1] = leftt[rightt[y + 1]] = leftt[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, (i + 1) * (d - max0) );
        }
    }

    cout << minArea;

    return 0;
}

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:53:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             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: 30 / 30
• Subtask 6: 25 / 25