fork(1) download
  1. #include <cstdio>
  2. #include <vector>
  3. #include <iostream>
  4. #include <set>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. #define MAXN 100005
  10.  
  11. int inf = 2000000000;
  12.  
  13. struct segment {
  14. int h, l, r;
  15. segment(){}
  16. segment(int h, int l, int r) : h(h), l(l), r(r) {}
  17. bool operator < (const segment &s) const {
  18. return h < s.h;
  19. }
  20. };
  21.  
  22. struct part {
  23. int l, r, f;
  24. segment s;
  25. part(int l, int r, int f, segment s) : l(l), r(r), f(f), s(s) {}
  26. bool operator < (const part &p) const {
  27. return l < p.l;
  28. }
  29. };
  30.  
  31. set<part> sweep;
  32. segment s[MAXN];
  33.  
  34. int main()
  35. {
  36. int n, t; scanf("%d %d", &n, &t);
  37. for(int i = 0; i < n; i++) {
  38. int h, l, r; scanf("%d %d %d", &h, &l, &r);
  39. s[i] = segment(h, l, r);
  40. }
  41. s[n] = segment(t, -inf, inf);
  42. sort(s, s+n);
  43.  
  44. part bottom(-inf, inf, inf, segment(0, -inf, inf));
  45. part left(-inf-1, -inf, 0, segment(0, -inf-1, -inf));
  46. part right(inf, inf+1, 0, segment(0, inf, inf+1));
  47. sweep.insert(bottom);
  48. sweep.insert(left);
  49. sweep.insert(right);
  50. for(int i = 0; i <= n; i++) {
  51. int h = s[i].h, l = s[i].l, r = s[i].r;
  52.  
  53. part p(l, r, 0, s[i]);
  54. set<part>::iterator it = sweep.upper_bound(p), jt, kt;
  55. it--;
  56. jt = it;
  57. set<part>::iterator lt = jt, rt = jt;
  58. lt--;
  59. rt++;
  60. while(jt->l < r) {
  61. if(!(lt->s.r > max(jt->s.l, l) && jt->s.h < lt->s.h && lt->s.h < h) &&
  62. !(rt->s.l < min(jt->s.r, r) && jt->s.h < rt->s.h && rt->s.h < h)) {
  63. p.f = max(p.f, min(jt->f, min(jt->s.r, r)-max(jt->s.l, l)));
  64. }
  65. lt++;
  66. jt++;
  67. rt++;
  68. }
  69.  
  70. kt = jt; kt--;
  71. part start = *it, end = *kt;
  72.  
  73. sweep.erase(it, jt);
  74. if(start.l<l) {
  75. sweep.insert(part(start.l, l, start.f, start.s));
  76. }
  77. if(end.r>r) {
  78. sweep.insert(part(r, end.r, end.f, end.s));
  79. }
  80. sweep.insert(p);
  81. }
  82.  
  83. set<part>::iterator it = sweep.begin();
  84. it++;
  85. printf("%d\n", it->f);
  86. }
  87.  
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout
Standard output is empty