Advertisement
Guest User

Untitled

a guest
Jan 21st, 2019
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int ans = 0, more = 0, less_ = 0;
  5.  
  6. struct event{
  7. int l, r, type, now_;
  8. event(){}
  9. event(int a, int b, int c, int d){
  10. l = a; r = b; type = c, now_ = d;
  11. }
  12. };
  13.  
  14. bool cmp(event a, event b){
  15. //if( ((a.type == 0) ? a.l : a.r) == ((b.type == 0) ? b.l : b.r)) return (a.type < b.type);
  16. //return (((a.type == 0) ? a.l : a.r) < ((b.type == 0) ? b.l : b.r));
  17. if(a.now_ == b.now_) return (a.type < b.type);
  18. return(a.now_ < b.now_);
  19. }
  20.  
  21. void upd(){
  22. if(less_ - more > ans) ans = less_ - more;
  23. }
  24.  
  25. signed main(){
  26. int n, t;
  27. cin >> n >> t;
  28. --t;
  29. vector<event> s;
  30. int a, b;
  31. for(int i = 0; i < n; ++i){
  32. cin >> a >> b;
  33. --a;
  34. s.push_back(event(a + 1, b, 0, a + 1));
  35. s.push_back(event(a + 1, b, 1, b));
  36. }
  37. sort(s.begin(), s.end(), cmp);
  38. // cout << s.size() << '\n';
  39. // for(auto i: s) cout << "<" << i.l << ", " << i.r << ", " << i.now_ << "> ";
  40. int start = 0, finish = 0, i2 = 0;
  41. //event q1, q2;
  42. for(start; start < s.size(); ++start){
  43. if(start > 0){
  44. if(start - 1 == finish && start < s.size()){
  45. ++finish;
  46. if(s[finish].type) more = max((long long)(0), more - 1);
  47. upd();
  48. }
  49. // q1 = s[finish], q2 = s[start - 1];
  50. if(s[start - 1].type == 0){
  51. if(s[finish].now_ <= s[start - 1].r) ++more;
  52. else max((long long)(0), less_ - 1);
  53. upd();
  54. }
  55. }
  56. upd();
  57. // cout << start << ' ' << finish << ' ' << less_ << ' ' << more << ' ' << ans << '\n';
  58. // q1 = s[finish + 1], q2 = s[start];
  59. while(finish < s.size() - 1 && s[finish + 1].now_ - s[start].now_ <= t) {
  60. ++finish;
  61. // q1 = s[finish];
  62. if(s[finish].type == 1){
  63. if(s[start].now_ <= s[finish].l) ++less_;
  64. else max((long long)(0), more - 1);
  65. upd();
  66. }
  67. // cout << " " << start << ' ' << finish << ' ' << ((q2.type == 0) ? q2.l : q2.l ) << ' ' << ((s[finish + 1].type == 0) ? s[finish + 1].l : s[finish + 1].l) << '\n';
  68. }
  69. upd();
  70. // cout << start << ' ' << finish << ' ' << less_ << ' ' << more << ' ' << ans << '\n';
  71. }
  72. cout << ans;
  73. return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement