SHARE
TWEET

Untitled

a guest Feb 14th, 2017 138 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <fstream>
  4. #include <cstring>
  5. #include <string>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <vector>
  9. #include <queue>
  10. #include <set>
  11. #include <map>
  12.  
  13. using namespace std;
  14.  
  15. const int MAXN = 100005;
  16. const int K = 4;
  17.  
  18. int n;
  19. int top[MAXN], bottom[MAXN], inverse[MAXN];
  20.  
  21. // dp[i] - furthest left we can build i crossroads.
  22. int dp[MAXN];
  23. int lis_len = 0;
  24.  
  25. int main() {
  26.     ifstream fin("nocross.in");
  27.     ofstream fout("nocross.out");
  28.  
  29.     fin >> n;
  30.     for (int i = 1; i <= n; ++i) {
  31.         fin >> top[i];
  32.         inverse[top[i]] = i;
  33.     }
  34.  
  35.     for (int i = 1; i <= n; ++i) {
  36.         fin >> bottom[i];
  37.     }
  38.  
  39.     lis_len = 0;
  40.     memset(dp, 0, sizeof(dp));
  41.     dp[0] = 0;
  42.  
  43.     for (int i = 1; i <= n; ++i) {
  44.         int cur = bottom[i];
  45.         vector<int> inds;
  46.         for (int j = min(n, cur + K); j >= max(1, cur - K); --j) {
  47.             // find the index of j on the top bank
  48.             inds.push_back(inverse[j]);
  49.         }
  50.  
  51.         // iterate from furthest right bridge to furthest left to avoid
  52.         // counting multiple bridges from the same source
  53.         sort(inds.begin(), inds.end());
  54.         for (int j = inds.size() - 1; j >= 0; --j) {
  55.             int top_ind = inds[j];
  56.             if (top_ind > dp[lis_len]) {
  57.                 // See if you can append it to the end
  58.                 ++lis_len;
  59.                 dp[lis_len] = top_ind;
  60.             } else if (top_ind < dp[1]){
  61.                 // See if this is the furthest left so far
  62.                 dp[1] = top_ind;
  63.             } else if (top_ind == dp[1]) {
  64.                 continue;
  65.             } else {
  66.                 // find the largest x such that dp[x] < top_ind
  67.                 int lo = 1;
  68.                 int hi = lis_len;
  69.  
  70.                 while (lo + 1 < hi) {
  71.                     int mid = lo + (hi - lo) / 2;
  72.                     if (dp[mid] < top_ind) {
  73.                         lo = mid;
  74.                     } else {
  75.                         hi = mid;
  76.                     }
  77.                 }
  78.  
  79.                 dp[hi] = top_ind;
  80.             }
  81.         }
  82.     }
  83.  
  84.     fout << lis_len << '\n';
  85.     return 0;
  86. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top