fork download
copy 
  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], pw2[MAX_N];
  28.  
  29. int main() {
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(0);
  32.     cout.tie(0);
  33.  
  34.     freopen("SETSEQ.inp", "r", stdin);
  35.     freopen("SETSEQ.out", "w", stdout);
  36.  
  37.     cin >> n >> m;
  38.  
  39.     for (int i = 1; i <= n; i++) {
  40.         cin >> a[i];
  41.     }
  42.  
  43.     for (int i = 1; i <= m; i++) {
  44.         cin >> b[i];
  45.     }
  46.  
  47.     bool chk = false;
  48.     pos[0] = 0;
  49.     for (int i = 1, j = 1; i <= n; i++) {
  50.         if (a[i] == b[j]) {
  51.             pos[j] = i;
  52.             if (++j == m + 1) {
  53.                 chk = true;
  54.                 break;
  55.             }
  56.         }
  57.     }
  58.  
  59.     if (!chk) {
  60.         cout << -1 << "\n";
  61.         return 0;
  62.     }
  63.  
  64.     pw2[0] = 1;
  65.     for (int i = 1; i <= n; i++) {
  66.         pw2[i] = pw2[i - 1] * 2 % MOD;
  67.     }
  68.  
  69.     int ans = m;
  70.     for (int i = m, j = n; i >= 1; i--) {
  71.         while (j >= pos[i - 1] + 1) {
  72.             update(a[j], pw2[n - j]);
  73.             j--;
  74.         }
  75.  
  76.         (ans += query(b[i] - 1)) %= MOD;
  77.     }
  78.  
  79.     cout << ans << "\n";
  80.  
  81.     return 0;
  82. }
  83.  
  84.  
Success #stdin #stdout 0.01s 6008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/L9MxK9
language:
C++14 (gcc 8.3)
created:
284 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!