fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int X = 1e6;
  5. const int INF = 1e8;
  6.  
  7. int cw(int a, int b) {
  8. 	return (b - a + X) % X;
  9. }
  10.  
  11. bool contains(int l, int r, int x) {
  12. 	return cw(l, x) + cw(x, r) == cw(l, r);
  13. }
  14.  
  15. struct point {
  16. 	int x, y;
  17. 	int c;
  18.  
  19. 	point() {}
  20. 	point(int x_, int y_, int c_) : x(x_), y(y_), c(c_) {}
  21.  
  22. 	bool operator < (const point& o) const {
  23. 		return x > o.x || (x == o.x && y > o.y);
  24. 	}
  25. };
  26.  
  27. struct node {
  28. 	node* c[2];
  29. 	int lx, rx;
  30. 	int maxv;
  31. 	int lazy;
  32.  
  33. 	void upd() {
  34. 		maxv = max(c[0]->maxv, c[1]->maxv) + lazy;
  35. 	}
  36. };
  37. node pool[12345];
  38. int node_idx;
  39.  
  40. node* init(int lx, int rx) {
  41. 	node* v = &pool[node_idx++];
  42. 	v->c[0] = v->c[1] = NULL;
  43. 	v->lx = lx; v->rx = rx;
  44. 	v->maxv = v->lazy = 0;
  45. 	if (lx + 1 == rx) {
  46. 		// leaf
  47. 	} else {
  48. 		v->c[0] = init(lx, (lx + rx) / 2);
  49. 		v->c[1] = init((lx + rx) / 2, rx);
  50. 	}
  51. 	return v;
  52. }
  53.  
  54. void upd_add(node* v, int ulx, int urx, int del) {
  55. 	if (urx <= v->lx || v->rx <= ulx) {
  56. 		return;
  57. 	} else if (ulx <= v->lx && v->rx <= urx) {
  58. 		v->maxv += del;
  59. 		v->lazy += del;
  60. 	} else {
  61. 		upd_add(v->c[0], ulx, urx, del);
  62. 		upd_add(v->c[1], ulx, urx, del);
  63. 		v->upd();
  64. 	}
  65. }
  66.  
  67. void upd_set(node* v, int x, int val) {
  68. 	if (v->lx + 1 == v->rx) {
  69. 		v->maxv = max(v->maxv, val);
  70. 	} else {
  71. 		val -= v->lazy;
  72. 		if (x < v->c[0]->rx) {
  73. 			upd_set(v->c[0], x, val);
  74. 		} else {
  75. 			upd_set(v->c[1], x, val);
  76. 		}
  77. 		v->upd();
  78. 	}
  79. }
  80.  
  81. int max_query(node* v, int qlx, int qrx) {
  82. 	if (qrx <= v->lx || v->rx <= qlx) {
  83. 		return -INF;
  84. 	} else if (qlx <= v->lx && v->rx <= qrx) {
  85. 		return v->maxv;
  86. 	} else {
  87. 		return v->lazy + max(
  88. 			max_query(v->c[0], qlx, qrx),
  89. 			max_query(v->c[1], qlx, qrx));
  90. 	}
  91. }
  92.  
  93. vector<int> ys;
  94. int solve(vector<point>& cnds) {
  95. 	int n = int(cnds.size());
  96. 	if (n == 0) return 0;
  97. 	ys.clear();
  98. 	for (int i = 0; i < n; i++) ys.push_back(cnds[i].y);
  99. 	sort(ys.begin(), ys.end());
  100. 	ys.erase(unique(ys.begin(), ys.end()), ys.end());
  101. 	sort(cnds.begin(), cnds.end());
  102. 	node_idx = 0;
  103. 	node* segtree = init(0, int(ys.size()));
  104. 	for (int i = 0; i < n; i++) {
  105. 		point& cur = cnds[i];
  106. 		int y = int(lower_bound(ys.begin(), ys.end(), cur.y) - ys.begin());
  107. 		if (cur.c == 0) {
  108. 			upd_add(segtree, y+1, int(ys.size()), 1);
  109. 			upd_set(segtree, y, max_query(segtree, 0, y+1) + 1);
  110. 		} else if (cur.c == 1) {
  111. 			upd_add(segtree, 0, y+1, 1);
  112. 		} else assert(false);
  113. 	}
  114. 	return segtree->maxv;
  115. }
  116.  
  117. vector<int> L, R;
  118.  
  119. void solve() {
  120. 	int n;
  121. 	cin >> n;
  122. 	L.resize(n);
  123. 	R.resize(n);
  124. 	for (int i = 0; i < n; i++) {
  125. 		cin >> L[i] >> R[i];
  126. 	}
  127. 	vector<point> cnds;
  128. 	cnds.reserve(n);
  129. 	int ans = 0;
  130. 	for (int i = 0; i < n; i++) {
  131. 		int dlr = cw(L[i], R[i]);
  132. 		int drl = cw(R[i], L[i]);
  133. 		int cur = 0;
  134. 		cnds.clear();
  135. 		for (int j = 0; j < n; j++) {
  136. 			bool cl = contains(L[j], R[j], L[i]);
  137. 			bool cr = contains(L[j], R[j], R[i]);
  138. 			if (cl && cr) {
  139. 				cur += 1;
  140. 			} else if (cl) {
  141. 				cnds.push_back(point(cw(L[i], R[j]), cw(L[j], L[i]), 1));
  142. 			} else if (cr) {
  143. 				cnds.push_back(point(dlr - cw(L[j], R[i]), drl - cw(R[i], R[j]), 0));
  144. 			}
  145. 		}
  146. 		cur += solve(cnds);
  147. 		ans = max(ans, cur);
  148. 	}
  149. 	cout << ans << '\n';
  150. }
  151.  
  152. int main() {
  153. 	ios::sync_with_stdio(0), cin.tie(0);
  154. 	int T;
  155. 	cin >> T;
  156. 	L.reserve(3000);
  157. 	R.reserve(3000);
  158. 	ys.reserve(3000);
  159. 	while (T--) solve();
  160. }
  161.  
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
1
4
1 4
4 5
5 2
3 3
stdout
copy 
3
https://ideone.com/M6Lx2a
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!