oj.uz

Submission #317495

# Submission time Handle Problem Language Result Execution time Memory
317495 2020-10-29T20:07:17 Z andremfq Golf (JOI17_golf) C++17
100 / 100
 4271 ms 521024 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 101 ms 150648 KB Output is correct
2 Correct 101 ms 150776 KB Output is correct
3 Correct 102 ms 150776 KB Output is correct
4 Correct 102 ms 150776 KB Output is correct
5 Correct 110 ms 151932 KB Output is correct
6 Correct 108 ms 152056 KB Output is correct
7 Correct 111 ms 151928 KB Output is correct
8 Correct 110 ms 151928 KB Output is correct
9 Correct 110 ms 151928 KB Output is correct
10 Correct 112 ms 151928 KB Output is correct
11 Correct 109 ms 151928 KB Output is correct
12 Correct 109 ms 151928 KB Output is correct
13 Correct 108 ms 151928 KB Output is correct
14 Correct 110 ms 152056 KB Output is correct
15 Correct 104 ms 151292 KB Output is correct
16 Correct 109 ms 152184 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 150648 KB Output is correct
2 Correct 101 ms 150776 KB Output is correct
3 Correct 102 ms 150776 KB Output is correct
4 Correct 102 ms 150776 KB Output is correct
5 Correct 110 ms 151932 KB Output is correct
6 Correct 108 ms 152056 KB Output is correct
7 Correct 111 ms 151928 KB Output is correct
8 Correct 110 ms 151928 KB Output is correct
9 Correct 110 ms 151928 KB Output is correct
10 Correct 112 ms 151928 KB Output is correct
11 Correct 109 ms 151928 KB Output is correct
12 Correct 109 ms 151928 KB Output is correct
13 Correct 108 ms 151928 KB Output is correct
14 Correct 110 ms 152056 KB Output is correct
15 Correct 104 ms 151292 KB Output is correct
16 Correct 109 ms 152184 KB Output is correct
17 Correct 114 ms 152440 KB Output is correct
18 Correct 111 ms 152312 KB Output is correct
19 Correct 111 ms 152440 KB Output is correct
20 Correct 112 ms 152440 KB Output is correct
21 Correct 112 ms 152568 KB Output is correct
22 Correct 119 ms 152440 KB Output is correct
23 Correct 110 ms 152440 KB Output is correct
24 Correct 115 ms 152440 KB Output is correct
25 Correct 112 ms 152440 KB Output is correct
26 Correct 111 ms 152444 KB Output is correct
27 Correct 105 ms 151544 KB Output is correct
28 Correct 111 ms 152312 KB Output is correct
29 Correct 110 ms 152312 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 150648 KB Output is correct
2 Correct 101 ms 150776 KB Output is correct
3 Correct 102 ms 150776 KB Output is correct
4 Correct 102 ms 150776 KB Output is correct
5 Correct 110 ms 151932 KB Output is correct
6 Correct 108 ms 152056 KB Output is correct
7 Correct 111 ms 151928 KB Output is correct
8 Correct 110 ms 151928 KB Output is correct
9 Correct 110 ms 151928 KB Output is correct
10 Correct 112 ms 151928 KB Output is correct
11 Correct 109 ms 151928 KB Output is correct
12 Correct 109 ms 151928 KB Output is correct
13 Correct 108 ms 151928 KB Output is correct
14 Correct 110 ms 152056 KB Output is correct
15 Correct 104 ms 151292 KB Output is correct
16 Correct 109 ms 152184 KB Output is correct
17 Correct 114 ms 152440 KB Output is correct
18 Correct 111 ms 152312 KB Output is correct
19 Correct 111 ms 152440 KB Output is correct
20 Correct 112 ms 152440 KB Output is correct
21 Correct 112 ms 152568 KB Output is correct
22 Correct 119 ms 152440 KB Output is correct
23 Correct 110 ms 152440 KB Output is correct
24 Correct 115 ms 152440 KB Output is correct
25 Correct 112 ms 152440 KB Output is correct
26 Correct 111 ms 152444 KB Output is correct
27 Correct 105 ms 151544 KB Output is correct
28 Correct 111 ms 152312 KB Output is correct
29 Correct 110 ms 152312 KB Output is correct
30 Correct 4103 ms 390136 KB Output is correct
31 Correct 4083 ms 389972 KB Output is correct
32 Correct 4172 ms 395500 KB Output is correct
33 Correct 4134 ms 393944 KB Output is correct
34 Correct 4207 ms 395004 KB Output is correct
35 Correct 4271 ms 396004 KB Output is correct
36 Correct 4172 ms 397336 KB Output is correct
37 Correct 4221 ms 398856 KB Output is correct
38 Correct 4214 ms 395496 KB Output is correct
39 Correct 4215 ms 398464 KB Output is correct
40 Correct 3221 ms 513768 KB Output is correct
41 Correct 3210 ms 513736 KB Output is correct
42 Correct 3269 ms 517360 KB Output is correct
43 Correct 3264 ms 517380 KB Output is correct
44 Correct 3275 ms 520892 KB Output is correct
45 Correct 3274 ms 520980 KB Output is correct
46 Correct 3300 ms 521024 KB Output is correct
47 Correct 3325 ms 520840 KB Output is correct
48 Correct 3328 ms 520828 KB Output is correct
49 Correct 3316 ms 520960 KB Output is correct
50 Correct 112 ms 152312 KB Output is correct
51 Correct 111 ms 152440 KB Output is correct
52 Correct 108 ms 152440 KB Output is correct