Guest User

Untitled

a guest
Apr 26th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. #define TASK "lcs"
  9. #define MAXN 50050
  10.  
  11. int n, a[2 * MAXN], b[2 * MAXN], c[MAXN][2], f[2 * MAXN], q[2 * MAXN];
  12. vector<pair<int, int> > p[2 * MAXN];
  13.  
  14. int get_max(int x)
  15. {
  16.     int res = 0;
  17.     for ( ; x >= 0; x &= x + 1, x--)
  18.         res = max(res, f[x]);
  19.     return res;
  20. }
  21.  
  22. void upgrade(int x, int p)
  23. {
  24.     for ( ; x < n; x |= x + 1)
  25.         f[x] = max(f[x], p);
  26. }
  27.  
  28. void upgrade(int x)
  29. {
  30.     int val = get_max(x - 1);
  31.     if (val + 1 > f[x])
  32.     {
  33.         int l = -1, r = x - 1, m = (l + r) >> 1;
  34.         while (r - l > 1)
  35.         {
  36.             if (get_max(m) == val)
  37.                 r = m;
  38.             else
  39.                 l = m;
  40.             m = (l + r) >> 1;
  41.         }
  42.         if (val > 0)
  43.             p[x].push_back(make_pair(r, (int)p[r].size() - 1));
  44.         upgrade(x, val + 1);
  45.         q[x] = val + 1;
  46.     }
  47. }
  48.  
  49. int main()
  50. {
  51.     ifstream cin(TASK".in");
  52.     ofstream cout(TASK".out");
  53.  
  54.     while (true)
  55.     {
  56.         cin >> n;
  57.         n <<= 1;
  58.         if (!n)
  59.             break;
  60.  
  61.         for (int i = 0; i < n; ++i)
  62.         {
  63.             cin >> a[i];
  64.             c[a[i]][0] = c[a[i]][1] = -1;
  65.         }
  66.         for (int i = 0; i < n; ++i)
  67.         {
  68.             cin >> b[i];
  69.             if (c[b[i]][1] == -1)
  70.                 c[b[i]][1] = i;
  71.             else
  72.                 c[b[i]][0] = i;
  73.             f[i] = q[i] = 0;
  74.             p[i].clear();
  75.         }
  76.  
  77.         for (int i = 0; i < n; ++i)
  78.         {
  79.             upgrade(c[a[i]][0]);
  80.             upgrade(c[a[i]][1]);
  81.         }
  82.  
  83.         int ans = get_max(n - 1);
  84.         cout << ans << endl;
  85.         vector<int> ansp;
  86.         pair<int, int> cur;
  87.         for (int i = n - 1; ; --i)
  88.             if (q[i] == ans)
  89.             {
  90.                 ansp.push_back(b[i]);
  91.                 cur = p[i][p[i].size() - 1];
  92.                 break;
  93.             }
  94.         for (int k = ans; ; cur = p[cur.first][cur.second])
  95.         {
  96.             ansp.push_back(b[cur.first]);
  97.             if (cur.second == -1 || p[cur.first].size() == 0)
  98.                 break;
  99.         }
  100.         for (vector<int>::reverse_iterator it = ansp.rbegin(); it != ansp.rend(); ++it)
  101.             cout << *it << " ";
  102.         cout << endl;
  103.     }
  104.  
  105.     return 0;
  106. }
Add Comment
Please, Sign In to add comment