fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define forr(i, l, r) for (int i = l; i<=r; i++)
  4. #define pii pair <ll, ll>
  5. #define f first
  6. #define s second
  7. using namespace std;
  8.  
  9.  
  10. int const N = 3e5 + 100;
  11. pii a[N];
  12. pii dp[N];
  13. pii c[N];
  14. ll n;
  15. ll tong, dem;
  16. int const mod = 1e9 + 7;
  17. pii tree[N];
  18. pii x;
  19. void add(ll& a, ll b)
  20. {
  21.     a += b;
  22.     if (a >= mod)
  23.         a-=mod;
  24. }
  25. void upd(ll i, pii v)
  26. {
  27.      for (; i <= dem; i += i & -i) {
  28. if (tree[i].f > v.f)
  29. {
  30.    tree[i] = v;
  31. }
  32. else if (tree[i].f == v.f)
  33. {
  34.     tree[i].f = v.f;
  35.     add(tree[i].s, v.s);
  36. }
  37. }
  38.  
  39. }
  40. pii query (ll i1)
  41. {
  42.     ll ans = 0;
  43.     ll res = 1e12;
  44.    ll i = i1;
  45.    for (; i; i -= i & -i)
  46.          res = min(res, tree[i].f);
  47. i = i1;
  48.     for (; i; i -= i & -i)
  49.    if (res == tree[i].f)
  50.     add(ans, tree[i].s);
  51.     return {res, ans};
  52. }
  53. ll b[N];
  54. bool ok[N];
  55. int main()
  56. {
  57. //    freopen("box.inp", " r", stdin);
  58. //    freopen("box.out", "w", stdout);
  59.     ios_base :: sync_with_stdio(false);
  60.      cin.tie(NULL);
  61.   cin >>n;
  62.   forr(i, 1, n) cin >>a[i].f >> a[i].s;
  63.   sort(a + 1, a + 1 + n, [&] (pii x, pii y)
  64.        {
  65.            if (x.s == y.s)
  66.         return x.f > y.f;
  67.            return x.s > y.s;
  68.        });
  69.   forr(i, 1, n) {
  70.    b[++dem] = a[i].f;
  71.    b[++dem] = a[i].s;
  72.   }
  73.   forr(i, 0, dem)
  74.   tree[i] = {1e12, 0};
  75. //  cout << tree[1].f << endl;
  76.    sort(b + 1, b + 1 + dem);
  77.    forr(i, 1, n) {
  78.    c[i].f = lower_bound(b + 1, b + 1 + dem, a[i].f) - b ;
  79.    c[i].s = lower_bound(b + 1, b + 1 + dem, a[i].s) - b ;
  80.    }
  81. //   forr(i, 1, n)
  82. //   cout << c[i] << " ";
  83.    ll minx = 1e12;
  84.  forr(i, 1, n)
  85.    { x = query(dem - c[i].f + 1);
  86.    if (x.f == 1e12 && x.s == 0) {
  87.     dp[i] = {a[i].s , 1};
  88.     minx = min(minx, dp[i].f);
  89.     ok[i] = 1;
  90. //    upd(c[i].f, dp[i]);
  91.    }
  92.     else {
  93.     dp[i] = {x.f + a[i].s - a[i].f, x.s};
  94.     minx = min(minx, x.f + a[i].s - a[i].f);
  95.     ok[i] = 0;
  96. //    cout << i << " " << x.f + a[i].s - a[i].f <<  endl;
  97.    }
  98.    upd(dem - c[i].s + 1, dp[i]);
  99.    }
  100. //  forr(i, 1, n)
  101. ////   if (dp[i].f )
  102. //  minx = min(dp[i].f + a[i].f , minx);
  103. //  forr(i, 1, n)
  104. //  cout << dp[i].f << " " << dp[i].s << endl;
  105. //cout << minx << endl;
  106. forr(i, 1, n)
  107. {
  108. //    cout << ok[i] << " " << dp[i].f << " " << i << " " << minx <<  endl;
  109. if (dp[i].f == minx)
  110.     add(tong, dp[i].s);
  111. //    if (ok[i])
  112. //    {
  113. //        if (dp[i].f == minx)
  114. //            add(tong, dp[i].s);
  115. //    }
  116. //    else
  117. //    {
  118. //        if (dp[i].f + a[i].f == minx)
  119. //            add(tong, dp[i].s);
  120. //    }
  121. }
  122.     cout << tong;
  123. //forr(i, 1, n)
  124. //dp[i] = 1;
  125. //forr(i, 1, n)
  126. //forr(j, i + 1, n)
  127. //if (a[i] <= a[j])
  128. //    dp[j] = min(dp[j], dp[i] + 1);
  129. //cout << dp[n];
  130. }
Success #stdin #stdout 0s 5628KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NAmfWy
language:
C++14 (gcc 8.3)
created:
16 hours 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!