Submission #317486

#	Time	Username	Problem	Language	Result	Execution time	Memory
317486		CaroLinda	Golf (JOI17_golf)	C++14	100 / 100	4143 ms	523372 KiB

golf

#include <bits/stdc++.h>

#define ll long long
#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()

const int MAXN = 4e5+200 ;
const int inf = 1e9+7 ;

using namespace std ;

struct Event
{

	// -1 = building opening
	// 1 = building closing

	int type ;
	int y , xMin , xMax ;

	Event(int type = 0 , int y = 0 ,int xMin = 0 , int xMax = 0 ) : type(type), y(y) , xMin(xMin), xMax(xMax) {}

	bool operator < (Event other) const 
	{
		//Don't care about ties because you will process in batches
		return y < other.y ;
	}

	void print() { printf("%d %d %d %d\n", type, y, xMin, xMax ) ; }

} ;                 

vector<Event> node ;
vector<bool> vis ;
int S , T , U , V ;
int n ;
int A[MAXN] , B[MAXN] , C[MAXN] , D[MAXN] ;
vector<int> sourceNodes , sinkNodes ;
vector<int> fila , dist ; // for the bfs
map<int,int> mp ;

struct Seg
{

	set< pair<int,int> > tree[MAXN*4] ;

	int m(int l, int r ) { return (l+r)>>1 ; }

	void insertLine(int pos, int l, int r , int beg, int en, pair<int,int> myPair )
	{
		if(l > en || r < beg ) return ;
		if( l >= beg && r <= en ) return (void)(tree[pos].insert(myPair) ) ;

		insertLine(pos<<1 , l, m(l,r) , beg, en, myPair ) ;
		insertLine(pos<<1|1 , m(l,r)+1, r, beg, en, myPair ) ;

	}

	void runThrough(int pos, int l, int r, int k , int beg, int en )
	{
		//I have to reach k in the seg
		//beg and en serve in the set

		auto it = tree[pos].lower_bound( make_pair(beg, -1 ) ) ;

		while( it != tree[pos].end() && it->first <= en )
		{
		
			if(!vis[it->second] )
			{
				vis[it->second] = true ;
				fila.push_back(it->second) ;
			}

			it++ ;
			
		}

		if( l == r ) return ;

		if(k <= m(l,r ) ) runThrough(pos<<1 , l, m(l,r) , k, beg, en ) ;
		else runThrough(pos<<1|1 , m(l,r)+1, r, k, beg, en ) ;

	}

	void goErasing(int pos, int l, int r, int beg, int en, pair<int,int> myPair )
	{
		if( l > en || r < beg ) return ;
		if(l >= beg && r <= en )
		{
			auto it = tree[pos].find( myPair ) ;
			tree[pos].erase(it) ;
			return ;
		}

		goErasing(pos<<1 , l, m(l,r) , beg, en, myPair ) ;
		goErasing(pos<<1|1 , m(l,r)+1, r, beg, en, myPair ) ;

	}


} seg[2] ;


void solve(int segIdx )
{
	
	//Remember to process in batch
	//So I won't mind about ties

	vector<Event> sweep ;
	set<int> points ;

  	for(int i = 1 ; i <= n ; i++ ) 
  	{
  		sweep.push_back( Event(-1, C[i] , A[i] , B[i]) ) ;
  		sweep.push_back( Event(1, D[i] , A[i] , B[i]) ) ;
  	}

  	sort(all(sweep) ) ;

  	points.insert( mp[0] ) ;
  	points.insert( mp[1e9+7] ) ;

	for(int i = 0 ; i < sz(sweep) ; )
	{
		int j = i ;

		while( j < sz(sweep) && sweep[j].y == sweep[i].y )
		{

			if( sweep[j].type == 1 && sweep[j].xMin != sweep[j].xMax )
			{
				points.erase( points.find(sweep[j].xMin) ) ;
				points.erase( points.find(sweep[j].xMax) ) ;
			}

			j++ ;
		}

		j = i ;

		while( j < sz(sweep) && sweep[j].y == sweep[i].y )
		{
			auto lef = points.lower_bound( sweep[j].xMin ) ;
			lef-- ;

			auto rig = points.upper_bound( sweep[j].xMax ) ;

			node.push_back( Event(segIdx, sweep[j].y , *lef, *rig) ) ;	

			if( sweep[j].xMin == sweep[j].xMax )
			{
				if(sweep[j].y == C[n-1] && sweep[j].xMin == A[n-1] )
					sourceNodes.push_back( sz(node) - 1 ) ;
				else sinkNodes.push_back( sz(node) - 1 ) ;
			}

			j++ ;

		}

		j = i ;
		while(j < sz(sweep) && sweep[j].y == sweep[i].y )
		{

			if( sweep[j].type == -1 && sweep[j].xMin != sweep[j].xMax)
			{
				points.insert( sweep[j].xMin ) ;
				points.insert( sweep[j].xMax ) ;
			}
			
	  		j++ ;
		}

		i = j ; 

	}
}

int main()
{
	
	scanf("%d %d %d %d", &S, &T, &U, &V ) ;	
	scanf("%d", &n ) ;

	for(int i = 1 ; i <= n ; i++ ) scanf("%d %d %d %d", &A[i] , &B[i] , &C[i] , &D[i] ) ;

	n++;
	A[n] = B[n] = S ;
	C[n] = D[n] = T ;

	n++ ;
	A[n] = B[n] = U ;
	C[n] = D[n] = V ;

	//Compression time :(
	//Never liked it

	mp[0] = 0 ;
	mp[1e9+7] = 0 ;

	for(int i = 1 ; i <= n ; i++ ) 
	{
		mp[ A[i] ] = 0 ;
		mp[ B[i] ] = 0 ;
		mp[ C[i] ] = 0 ;
		mp[ D[i] ] = 0 ;
	}

	int Key = 1 ;
	for(auto &e : mp ) e.second = Key++ ;
		
	for(int i = 1 ; i <= n ; i++ ) 
	{
		A[i] = mp[A[i]] ;
		B[i] = mp[B[i]] ;
		C[i] = mp[C[i]] ;
		D[i] = mp[D[i]] ;
	}

/*	printf("Debugging compression\n" ) ;
	for(int i = 1 ; i <= n ; i++  ) printf("%d %d %d %d\n", A[i] , B[i], C[i] , D[i] ) ;
	printf("\n") ; */

	//Supposed orientation
	solve(0) ;

	//Wrong orientation
	for(int i = 1 ; i <= n ; i++ ) 
	{
		swap(A[i] , C[i] ) ;
		swap(B[i] , D[i] ) ;
	}
	solve(1) ;

	for(int i = 1 ; i <= n ; i++ ) 
	{
		swap(A[i] , C[i] ) ;
		swap(B[i] , D[i] ) ;
	}


	int curNode = sz(node) ;

	for(int i = 0 ; i < curNode ; i++ )
		seg[ node[i].type ].insertLine( 1 ,  1  ,Key  , node[i].xMin , node[i].xMax , make_pair(node[i].y , i) ) ; 

	vis.resize( curNode ) ;
	dist.resize( curNode ) ;

	for(auto e : sourceNodes ) 
	{
		bool canReach = false ;

		if(node[e].type == 0 )
		{
			//That means I'm horizontal
			if( node[e].y == C[n] && node[e].xMin <= A[n] && node[e].xMax >= A[n] )
				canReach = true ;
		}

		else 
		{
			//I'm vertical
			if(node[e].y == A[n] && node[e].xMin <= C[n] && C[n] <= node[e].xMax )
				canReach = true ;
		}

		if(canReach)
		{
			printf("1\n") ;
			return 0 ;
		}

		fila.push_back( e ) ;
		vis[e] = true ;
		seg[ node[e].type ].goErasing( 1 , 1, Key , node[e].xMin , node[e].xMax , make_pair(node[e].y, e ) ) ;
	}

	int ini = 0 ;

	while(ini < sz(fila) )
	{
		int cur  = fila[ini++] ;

	//	printf("Now I am processing " ) ;
//		node[cur].print() ;     

		int last = sz(fila) ;
		int toLook = !node[cur].type ;

		seg[toLook].runThrough(1,1 , Key , node[cur].y , node[cur].xMin , node[cur].xMax ) ;

		for(int i = last ; i < sz(fila) ; i++ )
		{
			dist[fila[i]] = dist[cur]+1 ;
			seg[toLook].goErasing( 1 , 1 , Key, node[fila[i]].xMin, node[fila[i]].xMax, make_pair(node[fila[i]].y, fila[i] ) ) ;
		}
			
	}

	int ans = inf ;
	for(auto e : sinkNodes ) ans = min(ans, dist[e] ) ;

  printf("%d\n", ans+1 ) ;
	
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:184:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  184 |  scanf("%d %d %d %d", &S, &T, &U, &V ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:185:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  185 |  scanf("%d", &n ) ;
      |  ~~~~~^~~~~~~~~~~
golf.cpp:187:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  187 |  for(int i = 1 ; i <= n ; i++ ) scanf("%d %d %d %d", &A[i] , &B[i] , &C[i] , &D[i] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70