fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. #define           f     first
  6. #define           s     second
  7. #define           pb    push_back
  8. #define           ep    emplace
  9. #define           eb    emplace_back
  10. #define           lb    lower_bound
  11. #define           ub    upper_bound
  12. #define       all(x)    x.begin(), x.end()
  13. #define      rall(x)    x.rbegin(), x.rend()
  14. #define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
  15. #define     mem(f,x)    memset(f , x , sizeof(f))
  16. #define        sz(x)    (ll)(x).size()
  17. #define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
  18. #define          mxx    *max_element
  19. #define          mnn    *min_element
  20. #define    cntbit(x)    __builtin_popcountll(x)
  21. #define       len(x)    (int)(x.length())
  22.  
  23. const int N = 5e5 + 10;
  24. int x[N], y[N];
  25.  
  26. int lcs(vector <int> v) {
  27.     vector <int> cc;
  28.     for (auto x : v) {
  29.         if (sz(cc) == 0 || cc.back() < -x) {
  30.             cc.pb(-x);
  31.         } else {
  32.             int p = lower_bound(all(cc), -x) - cc.begin();
  33.             cc[p] = -x;
  34.         }
  35.     }
  36.  
  37.     return sz(cc);
  38. }
  39.  
  40. int main() {
  41.     ios_base::sync_with_stdio(0);
  42.     cin.tie(0);
  43.     cout.tie(0);
  44.  
  45.     int n;
  46.     cin >> n;
  47.  
  48.     for (int i = 1; i <= n; i++)
  49.         cin >> x[i] >> y[i];
  50.  
  51.  
  52.     vector <pair <int, int>> save;
  53.  
  54.     for (int i = 1; i <= n; i++) {
  55.         save.pb({x[i] - y[i], x[i] + y[i]});
  56.     }
  57.  
  58.     sort(all(save));
  59.  
  60.     vector <int> lst;
  61.     for (auto x : save) {
  62.         lst.pb(x.s);
  63.     }
  64.  
  65.     cout << lcs(lst) << '\n';
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/2kYzTk
language:
C++14 (gcc 8.3)
created:
273 days 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!