Posted in Segment Tree

POJ 2528

8/18/2017
Problem: http://poj.org/problem?id=2528
Solution: Segment tree, obviously. But since there’re 10^7 bricks, segment tree
only would bring up a MLE. That’s why we are using hashing: if no
endpoints of posters lie on segment a-b, it doesn’t really matter how
long this segment is. We can simply map it to a segment of length 2.
Note: In regard to the expression “a||b”, if a is already true then b would not
be checked. That’s where I spent two days debugging..


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

struct poster {
	int l, r;
} p[10100];

int x[20200] = {0};
int hash[10000010] = {0};
int nodecnt = 0;

struct node {
	int l, r;
	bool c;
	node *pl, *pr;
};

node tree[1000005];

void build (node *root, int l, int r) {
	root->c = false;
	root->l = l;
	root->r = r;
	if (l == r) {
		return;
	}
	nodecnt++;
	root->pl = tree + nodecnt;
	nodecnt++;
	root->pr = tree + nodecnt;
	int mid = (l + r) / 2;
	build(root->pl, l, mid);
	build(root->pr, mid + 1, r);
}

bool post (node *root, int l, int r) {
	// cout << root->l << ' ' << root->r << ' ' << root->c << endl;
	if (root->c) {
		return false;
	}
	if (root->l == l && root->r == r) {
		root->c = true;
		return true;
	}
	bool b = false;
	int mid = (root->l + root->r) / 2;
	if (r <= mid) {
		b = post(root->pl, l, r);
	} else if (l > mid) {
		b = post(root->pr, l, r);
	} else {
		bool b1 = post(root->pl, l, mid);
		bool b2 = post(root->pr, mid + 1, r);
		b = b1 || b2;
	}
	if (root->pl->c && root->pr->c) {
		root->c = true;
	}
	return b;
}

int main() {
	int c;
	scanf("%d", &c);
	while (c--) {
		memset(x, 0, sizeof(x));
		memset(hash, 0, sizeof(hash));
		memset(p, 0, sizeof(p));
		memset(tree, 0, sizeof(tree));
		nodecnt = 0;
		int n;
		scanf("%d", &n);
		// cout << n << endl;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &p[i].l, &p[i].r);
			x[cnt++] = p[i].l;
			x[cnt++] = p[i].r;
		} 
		sort(x, x + cnt);
		cnt = unique(x, x + cnt) - x;
//		for (int i = 0; i < cnt; i++) {
//			cout << x[i] << ' ';
//		}
		int no = 0;
		for (int i = 0; i < cnt; i++) {
//			cout << no << ' ';
			hash[x[i]] = no;
			if (i < cnt - 1) {
				if (x[i + 1] - x[i] == 1) {
					no++;
				} else {
					no += 2;
				}
			}
		}
		build(tree, 0, no);
		int ans = 0;
		for (int i = n - 1; i >= 0; i--) {
			// cout << hash[p[i].l] << ' ' << hash[p[i].r] << endl; 
			if (post(tree, hash[p[i].l], hash[p[i].r])) {
				ans++;
				// cout << i << endl;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s