• API
• FAQ
• Tools
• Archive
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;
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){
61.                 // See if this is the furthest left so far
62.                 dp = top_ind;
63.             } else if (top_ind == dp) {
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.
Not a member of Pastebin yet?