oj.uz

Submission #376469

# Submission time Handle Problem Language Result Execution time Memory
376469 2021-03-11T14:22:54 Z CaroLinda Cultivation (JOI17_cultivation) C++14
5 / 100
 2000 ms 376 KB 
#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() ;

	mx = max(mx, mnNorth+mnSouth) ;

	for(int i = mnNorth ; i <= R ; i++ )
		for(int j = mnSouth ; j <= R ; j++ )
			if( i+j >= mx ) test(i+j) ;

/*	for(int i = 1 ; i <= N ; i++ )
	{
		vector<int> vec = { seeds[i].first-1, R-seeds[i].first } ;

		for(int j = i ; j <= N ; j++ ) 
		{
			vec.push_back( seeds[j].first-seeds[i].first-1 ) ;
			vec.push_back( seeds[j].first-seeds[i].first ) ;
		}

		for(auto e : vec )
			if( e >= mx ) test(e) ;
	}  */

	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 ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Incorrect 3 ms 364 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Incorrect 3 ms 364 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Incorrect 3 ms 364 KB Output isn't correct
18 Halted 0 ms 0 KB -