oj.uz

Submission #317486

# Submission time Handle Problem Language Result Execution time Memory
317486 2020-10-29T19:10:55 Z CaroLinda Golf (JOI17_golf) C++14
100 / 100
 4143 ms 523372 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 150648 KB Output is correct
2 Correct 93 ms 150776 KB Output is correct
3 Correct 94 ms 150776 KB Output is correct
4 Correct 98 ms 150776 KB Output is correct
5 Correct 103 ms 151928 KB Output is correct
6 Correct 102 ms 151928 KB Output is correct
7 Correct 102 ms 151928 KB Output is correct
8 Correct 104 ms 152056 KB Output is correct
9 Correct 103 ms 151928 KB Output is correct
10 Correct 105 ms 151928 KB Output is correct
11 Correct 101 ms 151928 KB Output is correct
12 Correct 104 ms 151960 KB Output is correct
13 Correct 106 ms 151932 KB Output is correct
14 Correct 105 ms 151928 KB Output is correct
15 Correct 97 ms 151288 KB Output is correct
16 Correct 103 ms 152184 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 150648 KB Output is correct
2 Correct 93 ms 150776 KB Output is correct
3 Correct 94 ms 150776 KB Output is correct
4 Correct 98 ms 150776 KB Output is correct
5 Correct 103 ms 151928 KB Output is correct
6 Correct 102 ms 151928 KB Output is correct
7 Correct 102 ms 151928 KB Output is correct
8 Correct 104 ms 152056 KB Output is correct
9 Correct 103 ms 151928 KB Output is correct
10 Correct 105 ms 151928 KB Output is correct
11 Correct 101 ms 151928 KB Output is correct
12 Correct 104 ms 151960 KB Output is correct
13 Correct 106 ms 151932 KB Output is correct
14 Correct 105 ms 151928 KB Output is correct
15 Correct 97 ms 151288 KB Output is correct
16 Correct 103 ms 152184 KB Output is correct
17 Correct 105 ms 152440 KB Output is correct
18 Correct 104 ms 152312 KB Output is correct
19 Correct 105 ms 152568 KB Output is correct
20 Correct 105 ms 152444 KB Output is correct
21 Correct 104 ms 152440 KB Output is correct
22 Correct 106 ms 152440 KB Output is correct
23 Correct 106 ms 152440 KB Output is correct
24 Correct 105 ms 152440 KB Output is correct
25 Correct 106 ms 152440 KB Output is correct
26 Correct 107 ms 152440 KB Output is correct
27 Correct 97 ms 151672 KB Output is correct
28 Correct 104 ms 152312 KB Output is correct
29 Correct 103 ms 152312 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 150648 KB Output is correct
2 Correct 93 ms 150776 KB Output is correct
3 Correct 94 ms 150776 KB Output is correct
4 Correct 98 ms 150776 KB Output is correct
5 Correct 103 ms 151928 KB Output is correct
6 Correct 102 ms 151928 KB Output is correct
7 Correct 102 ms 151928 KB Output is correct
8 Correct 104 ms 152056 KB Output is correct
9 Correct 103 ms 151928 KB Output is correct
10 Correct 105 ms 151928 KB Output is correct
11 Correct 101 ms 151928 KB Output is correct
12 Correct 104 ms 151960 KB Output is correct
13 Correct 106 ms 151932 KB Output is correct
14 Correct 105 ms 151928 KB Output is correct
15 Correct 97 ms 151288 KB Output is correct
16 Correct 103 ms 152184 KB Output is correct
17 Correct 105 ms 152440 KB Output is correct
18 Correct 104 ms 152312 KB Output is correct
19 Correct 105 ms 152568 KB Output is correct
20 Correct 105 ms 152444 KB Output is correct
21 Correct 104 ms 152440 KB Output is correct
22 Correct 106 ms 152440 KB Output is correct
23 Correct 106 ms 152440 KB Output is correct
24 Correct 105 ms 152440 KB Output is correct
25 Correct 106 ms 152440 KB Output is correct
26 Correct 107 ms 152440 KB Output is correct
27 Correct 97 ms 151672 KB Output is correct
28 Correct 104 ms 152312 KB Output is correct
29 Correct 103 ms 152312 KB Output is correct
30 Correct 3944 ms 392252 KB Output is correct
31 Correct 3935 ms 391920 KB Output is correct
32 Correct 4086 ms 397472 KB Output is correct
33 Correct 4006 ms 396356 KB Output is correct
34 Correct 4070 ms 397212 KB Output is correct
35 Correct 4051 ms 398004 KB Output is correct
36 Correct 4093 ms 399516 KB Output is correct
37 Correct 4143 ms 401016 KB Output is correct
38 Correct 4041 ms 397732 KB Output is correct
39 Correct 4043 ms 400724 KB Output is correct
40 Correct 3196 ms 515976 KB Output is correct
41 Correct 3163 ms 515644 KB Output is correct
42 Correct 3242 ms 519592 KB Output is correct
43 Correct 3214 ms 519548 KB Output is correct
44 Correct 3257 ms 523176 KB Output is correct
45 Correct 3276 ms 523372 KB Output is correct
46 Correct 3237 ms 523208 KB Output is correct
47 Correct 3233 ms 523172 KB Output is correct
48 Correct 3272 ms 523248 KB Output is correct
49 Correct 3262 ms 523200 KB Output is correct
50 Correct 103 ms 152312 KB Output is correct
51 Correct 103 ms 152316 KB Output is correct
52 Correct 104 ms 152440 KB Output is correct