fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. pair<int, int> p[100001];
  7.  
  8. int n, m, dp[100001];
  9.  
  10. /*bool cmp(pair<int, int> &a, pair<int, int> &b){
  11.     if(a.first == b.first) a.second < b.second;
  12.     return a.first < b.first;
  13. }*/
  14.  
  15. void print(){
  16.     for(int j = 0; j < n; j++)
  17.         cout << p[j].first << " " << p[j].second << endl;
  18.     return;
  19. }
  20.  
  21. int foo(int l, int r, int left){
  22.     if(l == r) return l;
  23.     int mid = (l+r)/2;
  24.     if(p[mid].first >= left) return foo(l, mid, left);
  25.     return foo(mid+1, r, left);
  26. }
  27.  
  28. int recur(int curr){
  29.     if(curr == n-1) return (m - p[curr].second);
  30.     if(dp[curr] != -1) return dp[curr];
  31.     int left = p[curr].first, right = p[curr].second;
  32.     int pos = foo(curr + 1, n - 1, right);
  33.     while(pos < n && p[pos].first < right) pos++;
  34.  
  35.     int ans = m - right;
  36.     for(int j = pos; j < n; j++){
  37.         int curr_ans = p[j].first - right + recur(j);
  38.         ans = min(ans, curr_ans);
  39.     }
  40.     dp[curr] = ans;
  41.     return ans;
  42. }
  43.  
  44. void solve(){
  45.     print(); cout << endl;
  46.     sort(p, p+n);
  47.     print();
  48.  
  49.     int ans = 1000000001;
  50.     for(int j = 0; j < 100001; j++)
  51.         dp[j] = -1;
  52.  
  53.     for(int j = 0; j < n; j++)
  54.         ans = min(ans, p[j].first + recur(j));
  55.  
  56.     cout << ans << endl;
  57.     return;
  58. }
  59.  
  60. int main(){
  61.     ios_base :: sync_with_stdio(false);
  62.     cin.tie(NULL);
  63.  
  64.     cin >> n >> m;
  65.     for(int j = 0; j < n; j++)
  66.         cin >> p[j].first >> p[j].second;
  67.  
  68.     solve();
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 17224KB
comments (?)
stdin
copy 
5 15
2 4
3 7
1 5
13 15
6 9
stdout
copy 
2 4
3 7
1 5
13 15
6 9

1 5
2 4
3 7
6 9
13 15
6
https://ideone.com/avg4zX
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!