Submission #101075

#	Time	Username	Problem	Language	Result	Execution time	Memory
101075		ainta	Golf (JOI17_golf)	C++17	100 / 100	3798 ms	594928 KiB

golf

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#define pb push_back
#define N_ 101000
#define SZ 262144
using namespace std;
typedef pair<int, int> pii;
struct Rect {
	int bx,by,ex,ey;
}w[N_];
const int INF = 1e9 + 123;
int n, XX[2*N_], YY[2*N_], CX, CY;
void Flip() {
	for (int i = 1; i <= n; i++) {
		swap(w[i].bx, w[i].by);
		swap(w[i].ex, w[i].ey);
	}
}
struct Seg {
	int a, b, e;
	bool operator < (const Seg &p)const {
		return a < p.a;
	}
	bool operator ==(const Seg &p)const {
		return a == p.a&&b == p.b&&e == p.e;
	}
}U[N_][4];
struct Tree {
	int IT[SZ + SZ];
	void init() {
		for (int i = 0; i < SZ + SZ; i++)IT[i] = 0;
	}
	void Put(int b, int e, int x) {
		b += SZ, e += SZ;
		while (b <= e) {
			IT[b] = max(IT[b], x);
			IT[e] = max(IT[e], x);
			b = (b + 1) >> 1, e = (e - 1) >> 1;
		}
	}
	int Max(int x) {
		int r = 0;
		x += SZ;
		while (x) {
			r = max(r, IT[x]);
			x >>= 1;
		}
		return r;
	}
}TTT;

struct Seg2D {
	set<pii>Set[SZ + SZ];
	void Put(Seg tp, int num) {
		int b = tp.b+SZ, e = tp.e+SZ;
		while (b <= e) {
			if (b & 1) {
				Set[b].insert({ tp.a,num });
			}
			if (!(e & 1)) {
				Set[e].insert({ tp.a,num });
			}
			b = (b + 1) >> 1, e = (e - 1) >> 1;
		}
	}
	int Find(Seg tp) {
		int a = SZ + tp.a;
		while (a) {
			auto it = Set[a].lower_bound(pii(tp.b, -1));
			if (it != Set[a].end() && it->first <= tp.e) {
				return it->second;
			}
			a >>= 1;
		}
		return 0;
	}
	void Del(Seg tp, int num) {
		int b = tp.b + SZ, e = tp.e + SZ;
		while (b <= e) {
			if (b & 1) {
				Set[b].erase(pii(tp.a,num));
			}
			if (!(e & 1)) {
				Set[e].erase(pii(tp.a,num));
			}
			b = (b + 1) >> 1, e = (e - 1) >> 1;
		}
	}
}ST[2];

int D[SZ*2][2];
queue<pii>Q;

void Make(int swapped) {
	int i, cnt = 0;
	vector<Seg>V1, V2;
	for (i = 1; i <= n; i++) {
		V1.pb({ w[i].bx, w[i].by, w[i].ey });
		V1.pb({ w[i].ex, w[i].by, w[i].ey });
		if (i != 1) {
			V2.pb({ w[i].bx, w[i].by, i*2 });
			U[i][swapped * 2].a = w[i].by;
			V2.pb({ w[i].bx, w[i].ey, i*2+1 });
			U[i][swapped * 2 + 1].a = w[i].ey;
		}
	}
	sort(V1.begin(), V1.end());
	sort(V2.begin(), V2.end());
	TTT.init();
	int sz = V1.size(), pv = 0;
	for (int i = 0; i < V2.size(); i++) {
		auto t = V2[i];
		while (pv < sz && V1[pv].a < t.a) {
			TTT.Put(V1[pv].b + 1, V1[pv].e - 1, V1[pv].a);
			pv++;
		}
		int x = TTT.Max(t.b);
		U[t.e/2][swapped*2 + t.e%2].b = x;
	}
	TTT.init();
	pv = sz - 1;
	for (int i = V2.size() - 1; i >= 0; i--) {
		auto t = V2[i];
		while (pv >= 0 && V1[pv].a > t.a) {
			TTT.Put(V1[pv].b + 1, V1[pv].e - 1, CX + 1 - V1[pv].a);
			pv--;
		}
		int x = TTT.Max(t.b);
		U[t.e / 2][swapped * 2 + t.e % 2].e = CX + 1 - x;
	}
}
void Go(int num, int ck) {
	Seg a = U[num / 2][ck * 2 + num % 2];
	ST[ck].Del(a, num);
	Q.push(pii(num,ck));
}
int main() {
	int i, xx1,yy1,xx2,yy2, a;
	scanf("%d%d%d%d", &xx1,&yy1,&xx2,&yy2);
	w[1] = { -10, -10, INF, INF };
	w[2] = { xx1,yy1,xx1,yy1 };
	w[3] = { xx2,yy2,xx2,yy2 };
	scanf("%d", &n);
	n += 3;
	for (i = 4; i <= n; i++) {
		scanf("%d%d%d%d", &w[i].bx, &w[i].ex, &w[i].by, &w[i].ey);
	}
	for (i = 1; i <= n; i++) {
		XX[++CX] = w[i].bx, XX[++CX] = w[i].ex;
		YY[++CY] = w[i].by, YY[++CY] = w[i].ey;
	}
	sort(XX + 1, XX + CX + 1);
	sort(YY + 1, YY + CY + 1);
	for (i = 1; i <= n; i++) {
		w[i].bx = lower_bound(XX + 1, XX + CX + 1, w[i].bx) - XX;
		w[i].ex = lower_bound(XX + 1, XX + CX + 1, w[i].ex) - XX;
		w[i].by = lower_bound(YY + 1, YY + CY + 1, w[i].by) - YY;
		w[i].ey = lower_bound(YY + 1, YY + CY + 1, w[i].ey) - YY;
	}
	Make(0);
	Flip();
	Make(1);
	Flip();

	for (i = 2; i <= n; i++) {
		ST[0].Put(U[i][0], i*2);
		ST[0].Put(U[i][1], i*2+1);
		ST[1].Put(U[i][2], i*2);
		ST[1].Put(U[i][3], i*2+1);
	}
	Go(2 * 2, 0);
	Go(2 * 2, 1);
	while (!Q.empty()) {
		pii t = Q.front();
		Seg s = U[t.first / 2][t.second * 2 + t.first % 2];
		Q.pop();
		while (a = ST[1 - t.second].Find(s)) {
			D[a][1 - t.second] = D[t.first][t.second] + 1;
			Go(a, 1 - t.second);
		}
	}
	if (U[2][0] == U[3][0] || U[2][3] == U[3][3]) {
		puts("1");
		return 0;
	}

	printf("%d\n", min(D[3 * 2][0], D[3 * 2][1]) + 1);

	return 0;
}

Compilation message (stderr)

golf.cpp: In function 'void Make(int)':
golf.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V2.size(); i++) {
                  ~~^~~~~~~~~~~
golf.cpp:98:9: warning: unused variable 'cnt' [-Wunused-variable]
  int i, cnt = 0;
         ^~~
golf.cpp: In function 'int main()':
golf.cpp:180:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   while (a = ST[1 - t.second].Find(s)) {
          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &xx1,&yy1,&xx2,&yy2);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
golf.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &w[i].bx, &w[i].ex, &w[i].by, &w[i].ey);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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