Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define int long long
- using namespace std;
- signed main()
- {
- int n;
- cin>>n;
- vector<pair<int,int>>a(n+1);
- for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
- for(int i=1;i<=n;i++)a[i].second+=a[i].first;
- int ans=0;
- sort(a.begin()+1,a.end(),[&](pair<int,int>i,pair<int,int>j)
- {
- if(i.second!=j.second) return i.second<j.second;
- return i.first<j.first;
- });
- set<int>s,t;
- for(int i=1;i<=n;i++) s.insert(a[i].first);
- for(int i=1;i<=n;i++)
- {
- if(s.lower_bound(a[i].first)==s.end()) continue;
- while((t.find(*s.lower_bound(a[i].first))!=t.end())) s.erase(*s.lower_bound(a[i].first));
- if(s.lower_bound(a[i].first)==s.end()) continue;
- int k=*s.lower_bound(a[i].first);
- if(k>a[i].second) continue;
- ans++;
- s.erase(k);
- s.insert(k+1);
- t.insert(k);
- }
- cout<<ans<<'\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment