Submission #317363

#	Time	Username	Problem	Language	Result	Execution time	Memory
317363		CaroLinda	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1330 ms	17128 KiB

bulldozer

#include <bits/stdc++.h>
 
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
 
const int MAXN = 2010 ;
 
using namespace std ;
 
struct Seg
{
	
	long long soma[MAXN*4] ;
	long long bestLeft[MAXN*4] ;
	long long bestRight[MAXN*4] ;
	long long bestSum[MAXN*4] ;
 
	int m(int l, int r ) { return (l+r)>>1 ; }
 
	void print(int pos, int l, int r ) 
	{

		if(l == r ) return (void)(printf("%lld ", soma[pos] ) ) ;
 
		print(pos<<1 , l, m(l,r) ) ;
		print(pos<<1|1 , m(l,r)+1, r ) ;
 
	}
 
 
	void upd(int pos, int l, int r, int k, long long val ) //vamos de seg de setar?
	{
		if( l == r ) 
		{
			soma[pos] = val ;
			bestLeft[pos] = bestRight[pos] = bestSum[pos] = max(val, 0LL ) ;
			return ;
		}
 
		if( k <= m(l,r) ) upd(pos<<1 , l , m(l,r) , k, val ) ;
		else upd(pos<<1|1 , m(l,r)+1, r, k, val ) ;
 
		soma[pos] = soma[pos<<1] + soma[pos<<1|1] ;
		bestLeft[pos] = max(bestLeft[pos<<1|1] , soma[pos<<1|1] + bestLeft[pos<<1] ) ;
		bestRight[pos] = max(bestRight[pos<<1], soma[pos<<1] + bestRight[pos<<1|1] ) ;
		bestSum[pos] = bestLeft[pos<<1] + bestRight[pos<<1|1] ;
 
		bestSum[pos] = max(bestSum[pos<<1] ,max(bestSum[pos] , bestSum[pos<<1|1] ) ) ;
 
	}
 
	long long getAns() { return bestSum[1] ; }
 
} seg ;
 
int n ;
int pos[MAXN] ;
long long x[MAXN], y[MAXN] ;
long long w[MAXN] ;
 
int getFakeQuadrant(int i, int j )
{
	
	if( x[i] > x[j] ) return 0 ;
	if(x[i] == x[j] ) return 1 ;
	return 2 ;
 
}
 
struct Event
{
 
	int i , j ;
 
	Event(int i = 0 , int j = 0 ) : i(i) , j(j) {}
	
	bool operator < (Event other) const 
	{
		
		/* Tenho certeza que:
			i) y[i] > y[j]
			ii) y[i] == y[j] && x[i] > x[j]
 
			O numerador sempre vai ser positivo ou zero
		*/
 
		pair<long long,long long> mySlope = make_pair(y[i]-y[j], x[i]-x[j] ) ;
		pair<long long,long long> otherSlope = make_pair(y[other.i]-y[other.j], x[other.i]-x[other.j] ) ;
 
		int myFakeQuadrant =  getFakeQuadrant(i,j) ;
		int otherFakeQuadrant = getFakeQuadrant(other.i , other.j ) ;
 
		if(myFakeQuadrant != otherFakeQuadrant ) 
			return myFakeQuadrant < otherFakeQuadrant ;
 
		//Remember the denominators can be negative
		//And, therefore, the comparison will be weird	
 
		if( mySlope.first * otherSlope.second == mySlope.second * otherSlope.first )
		{
			//This will work even if there isn't a slope at all

			if( mySlope.first == 0 )
				return make_pair( x[i] , x[j] ) > make_pair( x[other.i] , x[other.j] ) ;

			return make_pair(y[i], y[j] ) > make_pair(y[other.i],  y[other.j] ) ;
		}
 
		if(mySlope.second < 0 ) 
		{
			mySlope.first = -mySlope.first ;
			mySlope.second = -mySlope.second ;
		}
		if(otherSlope.second < 0 )
		{
			otherSlope.first = -otherSlope.first ;
			otherSlope.second = -otherSlope.second ;
		}
 
		return mySlope.first * otherSlope.second < mySlope.second * otherSlope.first ;
		
	}
} ;
 
bool isEqual(Event a, Event b )
{
 
	pair<long long,long long> slope_a = make_pair( y[a.i] - y[a.j] , x[a.i] - x[a.j] ) ;
	pair<long long,long long> slope_b = make_pair( y[b.i] - y[b.j], x[b.i] - x[b.j] ) ;
 
	if( getFakeQuadrant(a.i, a.j ) != getFakeQuadrant(b.i, b.j ) )
		return false ;
 
	return slope_a.first * slope_b.second == slope_a.second * slope_b.first ;
 
}
     
int main()
{
	scanf("%d", &n ) ;
	for(int i = 1 ; i <= n ; i++ ) scanf("%lld %lld %lld", &x[i], &y[i] , &w[i] ) ;
 
	vector<int> initialSort(n) ;
	iota(all(initialSort),1) ;
	sort(all(initialSort), [&](int i, int j ) { 
	
		if( y[i] != y[j] ) return y[i] > y[j] ;
		return x[i] > x[j] ; 
 
	} ) ;
 
 //	for(int i = 0 ; i < n ; i++ ) cout << char(initialSort[i] + 'A' - 1 ) << " " ;
// 	cout << endl ;
 
	vector<Event> sweep ;
	
	for(int i = 0 ; i < n ; i++ ) pos[ initialSort[i] ] = i+1 ;
	
	for(int i = 0 ; i < n ; i++ )
		for(int j = i+1 ; j < n ; j++ )
			sweep.push_back(Event(initialSort[i],initialSort[j]) ) ;
 
	sort(all(sweep));
	//Depois eu crio a seg, vamos tentar entender os eventos primeiro
 
//	for(auto e : sweep ) cout << char(e.i + 'A'-1) << " " << char(e.j+'A'-1) << endl ;
 
	for(int i = 1 ; i <= n ; i++ ) seg.upd(1,1,n, pos[i] , w[i] ) ;
	
	long long ans = 0LL ;
	ans = max(ans, seg.getAns() ) ;
 
	for(int i = 0 ; i < sz(sweep ) ;  )
	{
		//initiating batch process
		int j = i ;
 
		while( j < sz(sweep) && isEqual(sweep[i], sweep[j] ) )
		{
			int u = sweep[j].i ;
			int v = sweep[j].j ;
 
			seg.upd(1 , 1 , n , pos[u] , w[v] ) ;
			seg.upd(1,1,n, pos[v], w[u] ) ;
 
			swap(pos[u], pos[v] ) ;
 
			j++ ;
		}		
 
		i = j ;
 
		/*cout << "After some lines"<< endl ;
		seg.print(1,1,n) ;
		cout << endl ; */
 
		ans = max(ans, seg.getAns() ) ;
	}
 
	printf("%lld\n", ans ) ;
 
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |  scanf("%d", &n ) ;
      |  ~~~~~^~~~~~~~~~~
bulldozer.cpp:142:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |  for(int i = 1 ; i <= n ; i++ ) scanf("%lld %lld %lld", &x[i], &y[i] , &w[i] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20