fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bka28U
language:
C++ (gcc 8.3)
created:
11 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!