Advertisement
Dang_Quan_10_Tin

DROPTEST

Apr 14th, 2022 (edited)
556
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #define task "DROPTEST"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. using ld = long double;
  10.  
  11. constexpr int N = 1e6 + 5;
  12. constexpr int Inf = 1e9 + 7;
  13. int n, f[N];
  14. int a[N], b[N];
  15.  
  16. void Read()
  17. {
  18.     cin >> n;
  19.  
  20.     for (int i = 1; i <= n; ++i)
  21.         cin >> a[i] >> b[i];
  22. }
  23.  
  24. void Solve()
  25. {
  26.     vector<int> s;
  27.     int ans(0);
  28.  
  29.     a[n + 1] = b[n + 1] = -Inf;
  30.  
  31.     for (int i = 1, j = 0; i <= n + 1; ++i)
  32.     {
  33.         int maxn = 1;
  34.  
  35.         while (!s.empty() && a[s.back()] <= a[i])
  36.         {
  37.             if (j < (int)s.size())
  38.                 maxn = max(maxn, f[s.back()] + i - s.back());
  39.  
  40.             s.pop_back();
  41.             j = min(j, (int)s.size());
  42.         }
  43.  
  44.         s.emplace_back(i);
  45.  
  46.         while (j < (int)s.size() && a[s[j]] > b[i])
  47.         {
  48.             ans = max(ans, f[s[j]] + i - s[j] - 1);
  49.             ++j;
  50.         }
  51.  
  52.         f[i] = maxn;
  53.     }
  54.  
  55.     cout << ans;
  56. }
  57.  
  58. int32_t main()
  59. {
  60.     ios_base::sync_with_stdio(0);
  61.     cin.tie(0);
  62.     cout.tie(0);
  63.  
  64.     if (fopen(task ".INP", "r"))
  65.     {
  66.         freopen(task ".INP", "r", stdin);
  67.         freopen(task ".OUT", "w", stdout);
  68.     }
  69.  
  70.     Read();
  71.     Solve();
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement