Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- int ans = 0, more = 0, less_ = 0;
- struct event{
- int l, r, type, now_;
- event(){}
- event(int a, int b, int c, int d){
- l = a; r = b; type = c, now_ = d;
- }
- };
- bool cmp(event a, event b){
- //if( ((a.type == 0) ? a.l : a.r) == ((b.type == 0) ? b.l : b.r)) return (a.type < b.type);
- //return (((a.type == 0) ? a.l : a.r) < ((b.type == 0) ? b.l : b.r));
- if(a.now_ == b.now_) return (a.type < b.type);
- return(a.now_ < b.now_);
- }
- void upd(){
- if(less_ - more > ans) ans = less_ - more;
- }
- signed main(){
- int n, t;
- cin >> n >> t;
- --t;
- vector<event> s;
- int a, b;
- for(int i = 0; i < n; ++i){
- cin >> a >> b;
- --a;
- s.push_back(event(a + 1, b, 0, a + 1));
- s.push_back(event(a + 1, b, 1, b));
- }
- sort(s.begin(), s.end(), cmp);
- // cout << s.size() << '\n';
- // for(auto i: s) cout << "<" << i.l << ", " << i.r << ", " << i.now_ << "> ";
- int start = 0, finish = 0, i2 = 0;
- //event q1, q2;
- for(start; start < s.size(); ++start){
- if(start > 0){
- if(start - 1 == finish && start < s.size()){
- ++finish;
- if(s[finish].type) more = max((long long)(0), more - 1);
- upd();
- }
- // q1 = s[finish], q2 = s[start - 1];
- if(s[start - 1].type == 0){
- if(s[finish].now_ <= s[start - 1].r) ++more;
- else max((long long)(0), less_ - 1);
- upd();
- }
- }
- upd();
- // cout << start << ' ' << finish << ' ' << less_ << ' ' << more << ' ' << ans << '\n';
- // q1 = s[finish + 1], q2 = s[start];
- while(finish < s.size() - 1 && s[finish + 1].now_ - s[start].now_ <= t) {
- ++finish;
- // q1 = s[finish];
- if(s[finish].type == 1){
- if(s[start].now_ <= s[finish].l) ++less_;
- else max((long long)(0), more - 1);
- upd();
- }
- // cout << " " << start << ' ' << finish << ' ' << ((q2.type == 0) ? q2.l : q2.l ) << ' ' << ((s[finish + 1].type == 0) ? s[finish + 1].l : s[finish + 1].l) << '\n';
- }
- upd();
- // cout << start << ' ' << finish << ' ' << less_ << ' ' << more << ' ' << ans << '\n';
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement