Submission #126857

#	Time	Username	Problem	Language	Result	Execution time	Memory
126857		sebinkim	Golf (JOI17_golf)	C++14	100 / 100	4295 ms	367128 KiB

golf

#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define compress(V) (sort((V).begin(), (V).end()), (V).erase(unique((V).begin(), (V).end()), (V).end()))
#define getcoor(V, x) (lb((V).begin(), (V).end(), (x)) - (V).begin())

using namespace std;

typedef pair <int, int> pii;

struct rect{
	int x1, x2, y1, y2;
	rect() {}
	rect(int x1, int x2, int y1, int y2) :
		x1(x1), x2(x2), y1(y1), y2(y2) {}
	bool operator == (rect &r)
		{ return x1 == r.x1 && x2 == r.x2 && y1 == r.y1 && y2 == r.y2; }
	void rotate() { swap(x1, y1); swap(x2, y2); }
};

struct segtree{
	set <pii> T[1101010];
	int sz = 1 << 19;
	
	void insert(int l, int r, int p, int i)
	{
		l += sz; r += sz;
		
		for(; l<=r; ){
			if(l & 1) T[l].insert(pii(p, i));
			if(~r & 1) T[r].insert(pii(p, i));
			l = l + 1 >> 1;
			r = r - 1 >> 1;
		}
	}
	
	void find(int p, int l, int r, queue <pii> &Q, int *C, int d)
	{
		for(p+=sz; p; p>>=1){
			for(; ; ){
				auto it = T[p].lower_bound(pii(l, -1));
				if(it == T[p].end() || it -> first > r) break;
				
				if(!C[it -> second]){
					C[it -> second] = 1;
					Q.push(pii(it -> second, d + 1));
				}
				T[p].erase(it);
			}
		}
	}
};

segtree _TX, _TY;
segtree *TX = &_TX, *TY = &_TY;
vector <rect> R, L;
set <int> S;
vector <pii> VI[404040], VO[404040];
vector <int> X, Y, V;
queue <pii> Q;
int C[1101010];
int n, x, y, sx, sy, ex, ey;
int vsx, vsy, vex, vey;

int main()
{
	int i, j, l, r, p, d;
	int x1, x2, y1, y2;
	
	scanf("%d%d%d%d%d", &sx, &sy, &ex, &ey, &n);
	
	X.pb(0); X.pb(2e9); Y.pb(0); Y.pb(2e9);
	X.pb(sx); X.pb(ex); Y.pb(sy); Y.pb(ey);
	
	for(i=0; i<n; i++){
		scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
		X.pb(x1); X.pb(x2); Y.pb(y1); Y.pb(y2);
		R.emplace_back(x1, x2, y1, y2);
	}
	
	compress(X); compress(Y);
	x = X.size(); y = Y.size();
	
	sx = getcoor(X, sx); sy = getcoor(Y, sy);
	ex = getcoor(X, ex); ey = getcoor(Y, ey);
	
	for(i=0; i<n; i++){
		R[i].x1 = getcoor(X, R[i].x1); R[i].x2 = getcoor(X, R[i].x2);
		R[i].y1 = getcoor(Y, R[i].y1); R[i].y2 = getcoor(Y, R[i].y2);
	}
	
	for(i=0; i<2; i++){
		S.clear();
		
		for(j=0; j<x; j++){
			VI[j].clear(); VO[j].clear();
		}
		
		for(rect &r: R){
			VI[r.x1].emplace_back(r.y1, r.y2);
			VO[r.x2].emplace_back(r.y1, r.y2);
		}
		
		S.clear();
		S.insert(0); S.insert(y - 1);
		
		for(j=0; j<x; j++){
			for(pii &t: VO[j]){
				S.erase(t.first); S.erase(t.second);
				l = *prev(S.lb(t.first)); r = *S.lb(t.second);
				L.emplace_back(j, j, l, r);
				TY -> insert(l, r, j, L.size() - 1);
			}
			
			if(sx == j){
				l = *prev(S.lb(sy)); r = *S.lb(sy);
				L.emplace_back(j, j, l, r);
				vsx = L.size() - 1;
			}
			
			if(ex == j){
				l = *prev(S.lb(ey)); r = *S.lb(ey);
				L.emplace_back(j, j, l, r);
				TY -> insert(l, r, j, L.size() - 1);
				vex = L.size() - 1;
			}
			
			for(pii &t: VI[j]){
				l = *prev(S.lb(t.first)); r = *S.lb(t.second);
				L.emplace_back(j, j, l, r);
				TY -> insert(l, r, j, L.size() - 1);
				S.insert(t.first); S.insert(t.second);
			}
		}
		
		swap(x, y); swap(X, Y); swap(TX, TY);
		swap(sx, sy); swap(ex, ey);
		swap(vsx, vsy); swap(vex, vey);
		
		for(rect &r: R) r.rotate();
		for(rect &r: L) r.rotate();
	}
	
	if(L[vsx] == L[vex] || L[vsy] == L[vey]){
		printf("1\n"); return 0;
	}
	
	Q.push(pii(vsx, 1)); Q.push(pii(vsy, 1));
	C[vsx] = 1; C[vsy] = 1;
	
	for(; !Q.empty(); ){
		tie(p, d) = Q.front(); Q.pop();
		if(p == vex || p == vey){
			printf("%d\n", d); return 0;
		}
		
		V.clear();
		
		if(L[p].x1 == L[p].x2) TX -> find(L[p].x1, L[p].y1, L[p].y2, Q, C, d);
		else TY -> find(L[p].y1, L[p].x1, L[p].x2, Q, C, d);
	}
	
	return 0;
}

Compilation message (stderr)

golf.cpp: In member function 'void segtree::insert(int, int, int, int)':
golf.cpp:34:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    l = l + 1 >> 1;
        ~~^~~
golf.cpp:35:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    r = r - 1 >> 1;
        ~~^~~
golf.cpp: In function 'int main()':
golf.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &sx, &sy, &ex, &ey, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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