fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.  
  12.     int n, m;
  13.     cin >> n >> m;
  14.  
  15.     vector<int> a(n), b(m);
  16.     vector<int> coords;
  17.     for (int i = 0; i < n; ++i) {
  18.         cin >> a[i];
  19.         coords.push_back(a[i]);
  20.     }
  21.     for (int i = 0; i < m; ++i) {
  22.         cin >> b[i];
  23.         coords.push_back(b[i]);
  24.     }
  25.  
  26.     sort(coords.begin(), coords.end());
  27.     coords.erase(unique(coords.begin(), coords.end()), coords.end());
  28.  
  29.     auto get_id = [&](int x) {
  30.         return lower_bound(coords.begin(), coords.end(), x) - coords.begin();
  31.     };
  32.  
  33.     for (int &x : a) x = get_id(x);
  34.     for (int &x : b) x = get_id(x);
  35.  
  36.     int k = coords.size();
  37.     vector<vector<int>> pos_a(k), pos_b(k);
  38.     for (int i = 0; i < n; ++i) pos_a[a[i]].push_back(i);
  39.     for (int i = 0; i < m; ++i) pos_b[b[i]].push_back(i);
  40.  
  41.     vector<vector<pair<int, int>>> pairs_a(k), pairs_b(k);
  42.     for (int i = 0; i < k; ++i) {
  43.         for (size_t j = 0; j + 1 < pos_a[i].size(); j += 2) {
  44.             pairs_a[i].push_back({pos_a[i][j], pos_a[i][j+1]});
  45.         }
  46.         for (size_t j = 0; j + 1 < pos_b[i].size(); j += 2) {
  47.             pairs_b[i].push_back({pos_b[i][j], pos_b[i][j+1]});
  48.         }
  49.     }
  50.  
  51.     vector<int> dp(m + 1, 0);
  52.     for (int i = 0; i < n; ++i) {
  53.         int val = a[i];
  54.         int first_occ = -1, second_occ = -1;
  55.  
  56.         size_t idx = lower_bound(pos_a[val].begin(), pos_a[val].end(), i) - pos_a[val].begin();
  57.         if (idx + 1 < pos_a[val].size()) {
  58.             first_occ = pos_a[val][idx];
  59.             second_occ = pos_a[val][idx+1];
  60.  
  61.             if (i == first_occ) {
  62.                 int current_max = 0;
  63.                 for (int j = 0; j < m; ++j) {
  64.                     if (b[j] == val) {
  65.                         size_t b_idx = lower_bound(pos_b[val].begin(), pos_b[val].end(), j) - pos_b[val].begin();
  66.                         if (b_idx + 1 < pos_b[val].size()) {
  67.                             int b_second = pos_b[val][b_idx + 1];
  68.                             int prev_val = current_max;
  69.                             dp[b_second + 1] = max(dp[b_second + 1], prev_val + 2);
  70.                         }
  71.                     }
  72.                     current_max = max(current_max, dp[j + 1]);
  73.                 }
  74.             }
  75.         }
  76.     }
  77.  
  78.     int result = 0;
  79.     for (int val : dp) result = max(result, val);
  80.     cout << result << endl;
  81.  
  82.     return 0;
  83. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
7 9
1 2 2 3 1 1 1
2 4 2 3 1 2 4 1 1
stdout
copy 
4
https://ideone.com/Dtlmi1
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!