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 n, m;
  9. int a[MAX_N], b[MAX_N];
  10. int pos[MAX_N], pw2[MAX_N];
  11.  
  12. int main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(0);
  15.     cout.tie(0);
  16.  
  17.     freopen("SETSEQ.inp", "r", stdin);
  18.     freopen("SETSEQ.out", "w", stdout);
  19.  
  20.     cin >> n >> m;
  21.  
  22.     for (int i = 1; i <= n; i++) {
  23.         cin >> a[i];
  24.     }
  25.  
  26.     for (int i = 1; i <= m; i++) {
  27.         cin >> b[i];
  28.     }
  29.  
  30.     bool chk = false;
  31.     pos[0] = 0;
  32.  
  33.     /// 2 1 3 4 5 
  34.     /// 2 6 
  35.  
  36.     for (int i = 1, j = 1; i <= n; i++) {
  37.         /// con trỏ i ở mảng a 
  38.         /// con trỏ j ở mảng b 
  39.         if (a[i] == b[j]) {
  40.             pos[j] = i;
  41.             if (++j == m + 1) {
  42.                 chk = true;
  43.                 break;
  44.             }
  45.         }
  46.     }
  47.  
  48.     if (!chk) {
  49.         cout << -1 << "\n";
  50.         return 0;
  51.     }
  52.  
  53.     pw2[0] = 1;
  54.     for (int i = 1; i <= n; i++) {
  55.         pw2[i] = pw2[i - 1] * 2 % MOD;
  56.     }
  57.  
  58.     /// c là các dãy con có thứ tự từ điển nhỏ hơn 
  59.  
  60.     int ans = m;
  61.     for (int i = 1; i <= m; i++) {
  62.         /// xét vị trí thứ i 
  63.         /// anh muốn mảng con c[i] < b[i] ngay tại vị trí i 
  64.         /// => c[i] < b[i] 
  65.  
  66.         /// 
  67.  
  68.         for (int j = pos[i - 1] + 1; j <= n; j++) {
  69.             /// anh check đuọc là a[j] < b[i] 
  70.             /// nếu ta lấy a[j] bỏ vô thì dãy con c luôn luôn có thứ tự tử điển nhỏ hơn b 
  71.             /// a[j + 1, n]
  72.  
  73.             /// 2 ^ (n - j) 
  74.  
  75.             if (a[j] < b[i]) {
  76.                 (ans += pw2[n - j]) %= MOD;
  77.             }
  78.         }
  79.     }
  80.  
  81.     cout << ans << "\n";
  82.  
  83.     return 0;
  84. }
  85.  
  86.  
Success #stdin #stdout 0.01s 5868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4qHFrO
language:
C++14 (gcc 8.3)
created:
6 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!