SHARE
TWEET

Untitled

a guest Feb 14th, 2020 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define left jkggh
  3. #define right fbjflkg
  4. #define ll long long
  5. #define db long double
  6. #define x first
  7. #define y second
  8. #define mp make_pair
  9. #define pb push_back
  10. #define all(a) a.begin(), a.end()
  11.  
  12. using namespace std;
  13.  
  14. struct Line{
  15.     int l; int r;
  16.     bool special;
  17. };
  18.  
  19. bool cmp(Line &a, Line &b) {
  20.     return (a.r < b.r);
  21. }
  22.  
  23. short dp[8003][8003][2];
  24.  
  25. bool sat(Line &right, Line &left) {
  26.     if (left.l < right.l && left.r > right.l && right.r > left.r) return true;
  27.     return false;
  28. }
  29.  
  30. int main(){
  31. #ifdef LOCAL
  32.     freopen("E_input.txt", "r", stdin);
  33.     //freopen("E_output.txt", "w", stdout);
  34. #endif
  35.     ios_base::sync_with_stdio(0);
  36.     cin.tie(0);
  37.  
  38.     int n, l;
  39.     cin >> n >> l;
  40.    
  41.     l--;
  42.  
  43.     vector<Line> v;
  44.  
  45.     for (int i = 0; i < n; ++i) {
  46.         int x, y;
  47.         cin >> x >> y;
  48.         v.push_back({x, y, false});
  49.         v.push_back({y+1, y+l+1, true});
  50.         v.push_back({x+1, x+l+1, true});
  51.         v.push_back({x-l+1, x+1, true});
  52.     }
  53.  
  54.     sort(v.begin(), v.end(), cmp);
  55.  
  56.  
  57.     for (int i = 0; i < v.size(); ++i) {
  58.         dp[i][0][v[i].special] = 1;
  59.  
  60.         int L = 0, R = v.size() + 1;
  61.         while (R-L>1) {
  62.             int M = (L+R)/2;
  63.             if (v[M-1].r < v[i].l) L = M;
  64.             else R = M;
  65.         }
  66.         int take = L;
  67.         for (int j = 0; j < i; ++j) {
  68.             if (!sat(v[i], v[j])) continue;
  69.             for (int was = 0; was <= 1; ++was) {
  70.                 int T = was + v[i].special;
  71.                 if (T==2) continue;
  72.                 dp[i][j+1][T] = dp[j][take][was] + 1;
  73.             }
  74.         }
  75.         for (int k = 0; k < 2; ++k) {
  76.             for (int j = 1; j <= i; ++j) {
  77.                 dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
  78.             }
  79.         }
  80.     }
  81.  
  82.     short mx = 0;
  83.     for (int i = 0; i < v.size(); ++i) {
  84.         mx = max(mx, dp[i][i][0]);
  85.         mx = max(mx, dp[i][i][1]);
  86.     }
  87.     cout << mx;
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top