fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX_N = 500005;
  6. const int MOD = 1e9 + 7;
  7.  
  8. int tree[MAX_N];
  9.  
  10. void update(int pos, int val) {
  11.     for (int i = pos; i < MAX_N; i += i & -i) {
  12.         (tree[i] += val) %= MOD;
  13.     }
  14. }
  15.  
  16. int query(int pos) {
  17.     int res = 0;
  18.     for (int i = pos; i > 0; i -= i & -i) {
  19.         (res += tree[i]) %= MOD;
  20.     }
  21.  
  22.     return res;
  23. }
  24.  
  25. int n, m;
  26. int a[MAX_N], b[MAX_N];
  27. int pos[MAX_N], dp[MAX_N], last[MAX_N];
  28.  
  29. int main() {
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(0);
  32.     cout.tie(0);
  33.  
  34.     freopen("SET.inp", "r", stdin);
  35.     freopen("SET.out", "w", stdout);
  36.  
  37.     int n, m;
  38.     cin >> n >> m;
  39.  
  40.     for (int i = 1; i <= n; i++) {
  41.         cin >> a[i];
  42.     }
  43.  
  44.     for (int i = 1; i <= m; i++) {
  45.         cin >> b[i];
  46.     }
  47.  
  48.     bool chk = false;
  49.     pos[0] = 0;
  50.     for (int i = 1, j = 1; i <= n; i++) {
  51.         if (a[i] == b[j]) {
  52.             pos[j] = i;
  53.             if (++j == m + 1) {
  54.                 chk = true;
  55.                 break;
  56.             }
  57.         }
  58.     }
  59.  
  60.     if (!chk) {
  61.         cout << -1 << "\n";
  62.         return 0;
  63.     }
  64.  
  65.     int ans = m;
  66.     dp[n + 1] = 1;
  67.     for (int i = m, j = n; i >= 1; i--) {
  68.         while (j >= pos[i - 1] + 1) {
  69.             dp[j] = 2 * dp[j + 1] % MOD;
  70.             if (last[a[j]]) {
  71.                 (dp[j] -= dp[last[a[j]] + 1] - MOD) %= MOD;
  72.                 update(a[j], -dp[last[a[j]] + 1] + MOD);
  73.             }
  74.  
  75.             update(a[j], dp[j + 1]);
  76.             last[a[j]] = j;
  77.             j--;
  78.         }
  79.         ///get [1, b[i] - 1] 
  80.  
  81.         /// it.get(1, 1, n, 1, b[i] - 1) 
  82.  
  83.         (ans += query(b[i] - 1)) %= MOD;
  84.     }
  85.  
  86.     cout << ans << "\n";
  87.  
  88.     return 0;
  89. }
  90.  
  91.  
Success #stdin #stdout 0.01s 5828KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ETKcuL
language:
C++14 (gcc 8.3)
created:
273 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!