[题解]ZOJ Monthly, July 2011beta » ZOJ3511

ZOJ3511
ZOJ3511.cpp


#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int MAXN = 1 << 14;

inline int L(int i) { return i << 1; }

inline int R(int i) { return L(i) ^ 1; }

struct SegTree {
	int m, a[MAXN << 1];

	void init(int n) {
		m = 1;
		while (m < n) {
			m <<= 1;
		}
		fill(a + m, a + m + m, 1);
		for (int i = m - 1; i > 0; --i) {
			a[i] = a[L(i)] + a[R(i)];
		}
	}

	void del(int p, int pl, int pr, int l, int r) {
		if (pl == l && pr == r) {
			a[p] = 0;
		} else {
			int pm = (pl + pr) / 2;
			if (r <= pm) {
				del(L(p), pl, pm, l, r);
			} else if (pm <= l) {
				del(R(p), pm, pr, l, r);
			} else {
				del(L(p), pl, pm, l, pm);
				del(R(p), pm, pr, pm, r);
			}
			a[p] = a[L(p)] + a[R(p)];
		}
	}

	void del(int l, int r) {
		if (l == r) {
			return;
		}
		del(1, 0, m, l, r);
	}

	int sum(int p, int pl, int pr, int l, int r) {
		if (a[p] == 0 || (pl == l && pr == r)) {
			return a[p];
		} else {
			int pm = (pl + pr) / 2;
			if (r <= pm) {
				return sum(L(p), pl, pm, l, r);
			} else if (pm <= l) {
				return sum(R(p), pm, pr, l, r);
			} else {
				return sum(L(p), pl, pm, l, pm) + sum(R(p), pm, pr, pm, r);
			}
		}
	}

	int sum(int l, int r) {
		return sum(1, 0, m, l, r);
	}
} st;

pair<int, PII> cut[MAXN];

int main() {
	int n, m, ans;

	while (scanf("%d%d", &n, &m) != EOF) {
		st.init(n);
		for (int i = 0; i < m; ++i) {
			scanf("%d%d", &cut[i].second.first, &cut[i].second.second);
			--cut[i].second.first;
			--cut[i].second.second;
			if (cut[i].second.first > cut[i].second.second) {
				swap(cut[i].second.first, cut[i].second.second);
			}
			cut[i].first = cut[i].second.second - cut[i].second.first;
			if (cut[i].first + cut[i].first > n) {
				cut[i].first = n - cut[i].first;
				swap(cut[i].second.first, cut[i].second.second);
			}
		}

		ans = 0;
		sort(cut, cut + m);
		for (int i = 0; i < m; ++i) {
			// printf("DO [%d, %d] %d\n", cut[i].second.first, cut[i].second.second, cut[i].first);
			if (cut[i].second.first > cut[i].second.second) {
				ans = max(ans, st.sum(cut[i].second.first, n) + st.sum(0, cut[i].second.second + 1));
				st.del(cut[i].second.first + 1, n);
				st.del(0, cut[i].second.second);
			} else {
				ans = max(ans, st.sum(cut[i].second.first, cut[i].second.second + 1));
				st.del(cut[i].second.first + 1, cut[i].second.second);
			}
		}
		ans = max(ans, st.sum(0, n));
		printf("%d\n", ans);
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//753 	2010-07-18 20:59:38 	Accepted 	1093 	C++ 	40 	500 	anotherpeg 	Source
Leave a Reply