fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6. #define all(x) begin(x), end(x)
  7. const int maxn = 4e5 + 42;
  8.  
  9. int hashed[maxn];
  10. vector<int> ops[2][maxn], cls[2][maxn];
  11. int inter[2][maxn];
  12.  
  13. int xr[2][4 * maxn];
  14. void add(int z, int p, int c, int v = 1, int l = 0, int r = maxn) {
  15. 	xr[z][v] += c;
  16. 	if(r - l > 1) {
  17. 		int m = (l + r) / 2;
  18. 		if(p < m) {
  19. 			add(z, p, c, 2 * v, l, m);
  20. 		} else {
  21. 			add(z, p, c, 2 * v + 1, m, r);
  22. 		}
  23. 	}
  24. }
  25. int get(int z, int a, int b, int v = 1, int l = 0, int r = maxn) {
  26. 	if(a <= l && r <= b) {
  27. 		return xr[z][v];
  28. 	} else if(r <= a || b <= l) {
  29. 		return 0;
  30. 	} else {
  31. 		int m = (l + r) / 2;
  32. 		return get(z, a, b, 2 * v, l, m) + get(z, a, v, 2 * v + 1, m, r);
  33. 	}
  34. }
  35.  
  36. void process(int *op, int *cl, int n, int z) {
  37. 	for(int i = 0; i < n; i++) {
  38. 		ops[z][op[i]].push_back(i);
  39. 		cls[z][cl[i]].push_back(i);
  40. 	}
  41. 	for(int i = 0; i < maxn; i++) {
  42. 		for(auto it: ops[z][i]) {
  43. 			add(z, cl[it], hashed[it]);
  44. 		}
  45. 		for(auto it: cls[z][i]) {
  46. 			inter[z][it] = get(z, op[it], maxn);
  47. 		}
  48. 	}
  49. }
  50.  
  51. signed main() {
  52.     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  53. 	//freopen("input.txt", "r", stdin);
  54. 	ios::sync_with_stdio(0);
  55. 	cin.tie(0);
  56. 	int n;
  57. 	cin >> n;
  58. 	int sa[n], ea[n], sb[n], eb[n];
  59. 	vector<int> alls;
  60. 	for(int i = 0; i < n; i++) {
  61. 		cin >> sa[i] >> ea[i] >> sb[i] >> eb[i];
  62. 		alls.insert(end(alls), {sa[i], ea[i], sb[i], eb[i]});
  63. 		hashed[i] = rng();
  64. 	}
  65. 	sort(all(alls));
  66. 	alls.erase(unique(all(alls)), end(alls));
  67. 	for(int i = 0; i < n; i++) {
  68. 		sa[i] = lower_bound(all(alls), sa[i]) - begin(alls);
  69. 		ea[i] = lower_bound(all(alls), ea[i]) - begin(alls);
  70. 		sb[i] = lower_bound(all(alls), sb[i]) - begin(alls);
  71. 		eb[i] = lower_bound(all(alls), eb[i]) - begin(alls);
  72. 	}
  73. 	process(sa, ea, n, 0);
  74. 	process(sb, eb, n, 1);
  75. 	for(int i = 0; i < n; i++) {
  76. 		if(inter[0][i] != inter[1][i]) {
  77. 			cout << "NO" << endl;
  78. 			return 0;
  79. 		}
  80. 	}
  81. 	cout << "YES" << endl;
  82. 	return 0;
  83. }
Runtime error #stdin #stdout 0.02s 40880KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Dypu4W
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!