fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int maxn = 1e6+5;
  5. const int mod = 1e9+7;
  6. typedef pair<int, int> ii;
  7. #define fi first
  8. #define se second
  9. #define read(_a, n) for(int i = 1; i <= n; i++) cin >> _a[i]
  10. #define For(i, _a, _b) for(int i = _a; i <= _b; i++)
  11. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  12. #define File(_x,_y) if (fopen(_x, "r")) freopen(_x, "r", stdin)//,freopen(_y, "w", stdout)
  13. #define file "main"
  14. #define bit(x, i) ((x >> i) & 1)
  15. #define bat(x, i) (x | (1 << i))
  16.  
  17. //a[i] = {cs, l, r}
  18.  
  19. int Rand(int l, int r)
  20. {
  21.     int ans = l + rand()%(r-l+1);
  22.     return ans;
  23. }
  24.  
  25. int n, m, dp[maxn], l[maxn], r[maxn];
  26. int T[maxn*4], res;
  27. int N = 4e6+5;
  28.  
  29. struct tp
  30. {
  31.     int cs;int l;int r;
  32. } a[maxn];
  33.  
  34. void update(int p, int v)
  35. {
  36.     while(p <= N)
  37.     {
  38.         T[p] = max(v, T[p]);
  39.         p += p&(-p);
  40.     }
  41. }
  42.  
  43. int get(int p)
  44. {
  45.     int res = 0;
  46.     while(p > 0)
  47.     {
  48.         res = max(res, T[p]);
  49.         p -= p&(-p);
  50.     }
  51.     return res;
  52. }
  53.  
  54. bool cmp(tp a, tp b)
  55. {
  56.     return a.cs - a.l < b.cs - b.l;
  57. }
  58.  
  59. int32_t main()
  60. {
  61.     fastIO;
  62.     File(file ".inp", file ".out");
  63.     cin >> n;
  64.     For(i, 1, n)
  65.     {
  66.         cin >> l[i] >> r[i];
  67.         a[i].cs = i;
  68.         a[i].l = l[i];
  69.         a[i].r = r[i];
  70.     }
  71.     sort(a+1, a+n+1, cmp);
  72.     int j = 0;
  73.     For(i, 1, n) dp[i] = 1;
  74.     For(i, 1, n)
  75.     {
  76.         while(j+1 < a[i].cs - a[i].l)
  77.         {
  78.             j++;
  79.            update(j + r[j], dp[j]);
  80.         }
  81.         dp[a[i].cs] = max(dp[a[i].cs], get(a[i].cs - 1) + 1);
  82.         res = max(dp[a[i].cs], res);
  83.     }
  84.     cout << res;
  85. }
  86.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RbHyk8
language:
C++14 (clang 8.0)
created:
14 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!