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
stdin
Standard input is empty
stdout
Standard output is empty