#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i= a ; i < b ; i++ )
#define pb push_back
const int MAXN = 310 ;
using namespace std ;
/*
O que acontece quando tem numa linha mais de uma coluna inserida?
Se eu fizer set vai dar zika
*/
int N , R , C , ans = INT_MAX ;
int mnNorth , mnSouth ;
int lefPref[MAXN] , rigPref[MAXN], midPref[MAXN] ;
int lefSuf[MAXN], rigSuf[MAXN], midSuf[MAXN] ;
pair<int,int> seeds[MAXN] ;
set< pair<int,int> > s ;
multiset<int> values ;
void add(int col, int id)
{
s.insert(make_pair(col,id) ) ;
auto it = s.find( make_pair(col,id) ) ;
auto it_less = it ; it_less-- ;
auto it_more = it ; it_more++ ;
if( it != s.begin() )
{
if( it_more != s.end() )
values.erase( values.find(it_more->first - it_less->first) ) ;
values.insert( col - it_less->first ) ;
}
if( it_more != s.end() )
values.insert( it_more->first - col ) ;
}
void rem(int col, int id )
{
auto it = s.find( make_pair(col, id) ) ;
auto it_less = it ; it_less-- ;
auto it_more = it ; it_more++ ;
if( it != s.begin() )
{
values.erase( values.find( col - it_less->first ) );
if( it_more != s.end() ) values.insert( it_more->first - it_less->first ) ;
}
if( it_more != s.end() ) values.erase( values.find(it_more->first - col) ) ;
s.erase( it ) ;
}
struct Event
{
int row , col , id , isClosing ;
Event(int row = 0 , int col = 0 , int id = 0 , int isClosing = 0 ) :
row(row), col(col) , id(id) , isClosing(isClosing) {}
bool operator < ( Event other ) const { return make_pair(row, isClosing) < make_pair(other.row, other.isClosing) ; }
} ;
void test(int x)
{
int mx = 0 ;
int west_min = 0 , east_min = 0 ;
int north = x-mnSouth , south = mnSouth ;
vector< Event > sweep ;
for(int i= 1 ; i <= N ; i++ )
{
sweep.push_back( Event( max(1, seeds[i].first-north) , seeds[i].second , i , 0 ) ) ;
sweep.push_back( Event( min(seeds[i].first + south,R) , seeds[i].second , i , 1 ) ) ;
if( seeds[i].first+south+1 <= R )
sweep.push_back( Event( seeds[i].first +south+1 , seeds[i].second , i , -1 ) ) ;
}
sort(all(sweep) ) ;
for(int i = 0 , ptr = 0 ; i < sz(sweep) ; i = ptr )
{
int r = sweep[i].row ;
while( ptr < sz(sweep) && sweep[ptr].row == r && sweep[ptr].isClosing != 1 )
{
if( sweep[ptr].isClosing == 0 )
add( sweep[ptr].col , sweep[ptr].id ) ;
ptr++ ;
}
if( r != 1 && r != R )
{
west_min = max(west_min , s.begin()->first - 1 ) ;
east_min = max(east_min, C - prev(s.end() )->first ) ;
int k = ( values.empty() ) ? 0 : *prev(values.end() ) ;
mx = max(mx, k-1) ;
}
while( ptr < sz(sweep) && sweep[ptr].row == r )
{
if( sweep[ptr].isClosing == 1 )
rem(sweep[ptr].col , sweep[ptr].id ) ;
ptr++ ;
}
}
int tempAns = INT_MAX ;
int ptrSuf = N ;
while( ptrSuf && R-seeds[ptrSuf].first + mnNorth <= x ) ptrSuf-- ;
ptrSuf++ ;
for(int i = 1 ; i <= N ; i++ )
{
while( ptrSuf <= N && x-seeds[i].first+1 < R-seeds[ptrSuf].first ) ptrSuf++ ;
if( ptrSuf > N ) break ;
int west_minTemp = max( lefPref[i], lefSuf[ptrSuf] ) ;
west_minTemp = max( west_minTemp , west_min ) ;
int east_minTemp = max(rigPref[i], rigSuf[ptrSuf] ) ;
east_minTemp = max(east_minTemp , east_min ) ;
int mxTemp = max( midPref[i], midSuf[ptrSuf] ) ;
mxTemp = max(mxTemp, mx ) ;
tempAns = min(tempAns, max(mxTemp, east_minTemp + west_minTemp ) ) ;
}
ans = min( ans , x+tempAns) ;
}
int main()
{
scanf("%d %d %d", &R, &C, &N ) ;
for(int i = 1 ; i <= N ; i++ ) scanf("%d %d", &seeds[i].first, &seeds[i].second ) ;
sort(seeds+1, seeds+1+N) ;
int mx = 0 ;
for(int i= 1 ; i < N ; i++ ) mx = max(mx, seeds[i+1].first-seeds[i].first-1 ) ;
mnNorth = seeds[1].first-1 ;
mnSouth = R-seeds[N].first ;
int mnCol = INT_MAX ;
int mxCol = -1 ;
for(int i = 1 ; i<= N ; i++ )
{
mnCol = min( mnCol , seeds[i].second ) ;
mxCol = max(mxCol, seeds[i].second ) ;
add( seeds[i].second , i ) ;
lefPref[i] = mnCol - 1;
rigPref[i] = C-mxCol ;
midPref[i] = ( values.empty() ) ? 0 : (*prev( values.end() )-1 ) ;
}
values.clear() ;
s.clear() ;
mnCol = INT_MAX ;
mxCol = -1 ;
for(int i = N ; i > 0 ; i-- )
{
mnCol = min( mnCol, seeds[i].second ) ;
mxCol = max(mxCol, seeds[i].second ) ;
add( seeds[i].second , i ) ;
lefSuf[i] = mnCol - 1 ;
rigSuf[i] = C-mxCol ;
midSuf[i] = ( values.empty() ) ? 0 : (*prev( values.end() )-1 ) ;
}
values.clear() ;
s.clear() ;
for(int i = 1 ; i <= N ; i++ )
{
for(int j = 1 ; j <= N ; j++ )
{
int delta_row = seeds[i].first - seeds[j].first - 1 ;
if( delta_row >= max( mnNorth + mnSouth , mx) ) test(delta_row) ;
}
if( seeds[i].first-1 >= max(mnNorth+mnSouth, mx) ) test(seeds[i].first-1) ;
if( R-seeds[i].first >= max(mnNorth+mnSouth, mx) ) test(R-seeds[i].first) ;
}
printf("%d\n", ans ) ;
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:154:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
154 | scanf("%d %d %d", &R, &C, &N ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:155:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
155 | for(int i = 1 ; i <= N ; i++ ) scanf("%d %d", &seeds[i].first, &seeds[i].second ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
