Ankit_132

D

Oct 21st, 2023
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. signed main()
  7. {
  8.   int n;
  9.   cin>>n;
  10.  
  11.   vector<pair<int,int>>a(n+1);
  12.  
  13.   for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
  14.   for(int i=1;i<=n;i++)a[i].second+=a[i].first;
  15.  
  16.   int ans=0;
  17.  
  18.   sort(a.begin()+1,a.end(),[&](pair<int,int>i,pair<int,int>j)
  19.   {
  20.       if(i.second!=j.second)    return i.second<j.second;
  21.       return                    i.first<j.first;
  22.   });
  23.  
  24.   set<int>s,t;
  25.  
  26.   for(int i=1;i<=n;i++)       s.insert(a[i].first);
  27.  
  28.   for(int i=1;i<=n;i++)
  29.   {
  30.       if(s.lower_bound(a[i].first)==s.end())                continue;
  31.       while((t.find(*s.lower_bound(a[i].first))!=t.end()))  s.erase(*s.lower_bound(a[i].first));
  32.       if(s.lower_bound(a[i].first)==s.end())                continue;
  33.      
  34.       int k=*s.lower_bound(a[i].first);
  35.      
  36.       if(k>a[i].second)                                     continue;
  37.      
  38.       ans++;
  39.      
  40.       s.erase(k);
  41.       s.insert(k+1);
  42.       t.insert(k);
  43.   }
  44.  
  45.   cout<<ans<<'\n';
  46. }
Advertisement
Add Comment
Please, Sign In to add comment