Submission #122889

#	Time	Username	Problem	Language	Result	Execution time	Memory
122889		youngyojun	Golf (JOI17_golf)	C++11	100 / 100	4310 ms	261508 KiB

golf

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 100055;
const int MX = 262144;

struct LNE {
	LNE(int x, int sy, int ey, bool isf = false)
		: x(x), sy(sy), ey(ey), isf(isf) {}
	int x, sy, ey;
	bool isf;

	bool operator < (const LNE &t) const {
		return x < t.x;
	}
	bool operator == (const LNE &t) const {
		return x == t.x && sy == t.sy && ey == t.ey;
	}
};

struct SEG {
	set<pii> d[MX*2];

	void push(int x, int y, int i) { d[x].insert({y, i}); }
	void push(int s, int e, int y, int i) {
		for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) push(s++, y, i);
			if(~e&1) push(e--, y, i);
		}
	}
	void pop(int x, int y, int i) { d[x].erase({y, i}); }
	void pop(int s, int e, int y, int i) {
		for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) pop(s++, y, i);
			if(~e&1) pop(e--, y, i);
		}
	}
	int get(int x, int s, int e) {
		for(x += MX; x; x >>= 1) {
			auto it = d[x].lower_bound({s, -1});
			if(d[x].end() != it && it->first <= e)
				return it->second;
		}
		return -1;
	}
} segX, segY;

vector<LNE> LXV, LYV;
int DX[MAXN*2], DY[MAXN*2];

int SX[MAXN], SY[MAXN], EX[MAXN], EY[MAXN];

int PSX, PSY, PEX, PEY;
int SXI, SYI, EXI, EYI;
int N;

void compress() {
	vector<int> V;
	auto f = [&](int x) { return int(lower_bound(allv(V), x) - V.begin()) + 1; };
	V.eb(PSX); V.eb(PEX);
	for(int i = 1; i <= N; i++) {
		V.eb(SX[i]);
		V.eb(EX[i]);
	}
	sorv(V); univ(V);
	PSX = f(PSX); PEX = f(PEX);
	for(int i = 1; i <= N; i++) {
		SX[i] = f(SX[i]);
		EX[i] = f(EX[i]);
	}
	V.clear(); V.eb(PSY); V.eb(PEY);
	for(int i = 1; i <= N; i++) {
		V.eb(SY[i]);
		V.eb(EY[i]);
	}
	sorv(V); univ(V);
	PSY = f(PSY); PEY = f(PEY);
	for(int i = 1; i <= N; i++) {
		SY[i] = f(SY[i]);
		EY[i] = f(EY[i]);
	}
}

void makeLines(vector<LNE> &EV, vector<LNE> &LV) {
	set<int> CH;
	sorv(EV);
	CH.insert(0); CH.insert((N+1)<<1|1);
	for(int s = 0, e, x, n = sz(EV); s < n; s = e) {
		x = EV[s].x;
		for(e = s+1; e < n && x == EV[e].x; e++);
		for(int i = s; i < e; i++) if(EV[i].sy != EV[i].ey) {
			CH.erase(EV[i].sy);
			CH.erase(EV[i].ey);
		}
		for(int i = s; i < e; i++) {
			auto it = CH.lower_bound(EV[i].sy);
			LV.eb(x, *prev(it), *it);
		}
		for(int i = s; i < e; i++) if(EV[i].isf) {
			CH.insert(EV[i].sy);
			CH.insert(EV[i].ey);
		}
	}
	sorv(LV); univ(LV);
}

void makeLines() {
	vector<LNE> V;
	V.eb(PSX, PSY, PSY); V.eb(PEX, PEY, PEY);
	for(int i = 1; i <= N; i++) {
		V.eb(SX[i], SY[i], EY[i], true);
		V.eb(EX[i], SY[i], EY[i]);
	}
	makeLines(V, LYV);
	V.clear();
	V.eb(PSY, PSX, PSX); V.eb(PEY, PEX, PEX);
	for(int i = 1; i <= N; i++) {
		V.eb(SY[i], SX[i], EX[i], true);
		V.eb(EY[i], SX[i], EX[i]);
	}
	makeLines(V, LXV);
}

void pushLX(int i) { segX.push(LXV[i].sy, LXV[i].ey, LXV[i].x, i); }
void pushLY(int i) { segY.push(LYV[i].sy, LYV[i].ey, LYV[i].x, i); }
void popLX(int i) { segX.pop(LXV[i].sy, LXV[i].ey, LXV[i].x, i); }
void popLY(int i) { segY.pop(LYV[i].sy, LYV[i].ey, LYV[i].x, i); }

int getAns() {
	fill(DX, DX+MAXN*2, INF);
	fill(DY, DY+MAXN*2, INF);

	queue<int> PQ;
	DX[SXI] = 1; DY[SYI] = 1;
	PQ.push(SXI<<1);
	PQ.push(SYI<<1|1);
	popLX(SXI); popLY(SYI);
	for(int idx, dst; !PQ.empty();) {
		idx = PQ.front(); PQ.pop();
		if(idx&1) {
			idx >>= 1;
			dst = DY[idx] + 1;
			for(int v;;) {
				v = segX.get(LYV[idx].x, LYV[idx].sy, LYV[idx].ey);
				if(v < 0) break;
				DX[v] = dst;
				popLX(v);
				PQ.push(v<<1);
			}
		} else {
			idx >>= 1;
			dst = DX[idx] + 1;
			for(int v;;) {
				v = segY.get(LXV[idx].x, LXV[idx].sy, LXV[idx].ey);
				if(v < 0) break;
				DY[v] = dst;
				popLY(v);
				PQ.push(v<<1|1);
			}
		}
	}

	return min(DX[EXI], DY[EYI]);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> PSX >> PSY >> PEX >> PEY >> N;
	for(int i = 1; i <= N; i++)
		cin >> SX[i] >> EX[i] >> SY[i] >> EY[i];
	
	compress();
	makeLines();
	SXI = EXI = SYI = EYI = -1;
	for(int i = sz(LXV); i--;) {
		pushLX(i);
		if(LXV[i].sy <= PSX && PSX <= LXV[i].ey && LXV[i].x == PSY) SXI = i;
		if(LXV[i].sy <= PEX && PEX <= LXV[i].ey && LXV[i].x == PEY) EXI = i;
	}
	for(int i = sz(LYV); i--;) {
		pushLY(i);
		if(LYV[i].x == PSX && LYV[i].sy <= PSY && PSY <= LYV[i].ey) SYI = i;
		if(LYV[i].x == PEX && LYV[i].sy <= PEY && PEY <= LYV[i].ey) EYI = i;
	}

	cout << getAns() << endl;
	return 0;
}

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