fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. const int N = 2e5 + 5;
  10. const int M = 2e3 + 5;
  11.  
  12. const int NUM_BLOCKS = (M / 64) + 2; 
  13.  
  14. struct Bitset {
  15.     unsigned long long data[NUM_BLOCKS];
  16.  
  17.     Bitset() {
  18.         memset(data, 0, sizeof(data));
  19.     }
  20.  
  21.     void set_bit(int pos) {
  22.         data[pos >> 6] |= (1ULL << (pos & 63));
  23.     }
  24.  
  25.     int count() {
  26.         int res = 0;
  27.         for (int i = 0; i < NUM_BLOCKS; ++i) {
  28.             res += __builtin_popcountll(data[i]);
  29.         }
  30.         return res;
  31.     }
  32.  
  33.     void update(const Bitset &Match) {
  34.         unsigned long long borrow = 0;
  35.         unsigned long long carry_shift = 1; 
  36.  
  37.         for (int i = 0; i < NUM_BLOCKS; ++i) {
  38.             unsigned long long X = data[i] | Match.data[i];
  39.  
  40.             unsigned long long shifted = (data[i] << 1) | carry_shift;
  41.             carry_shift = (data[i] >> 63); 
  42.             unsigned long long Y = shifted;
  43.  
  44.  
  45.             unsigned long long diff = X - Y - borrow;
  46.  
  47.             if (X < Y || (X == Y && borrow)) {
  48.                 borrow = 1;
  49.             } else {
  50.                 borrow = 0;
  51.             }
  52.  
  53.             data[i] = X & (X ^ diff);
  54.         }
  55.     }
  56. };
  57.  
  58. int n, m;
  59. int a[N], b[M];
  60. Bitset P[M + 5]; 
  61.  
  62. int main() {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0); cout.tie(0);
  65.  
  66.     int t; 
  67.     if (!(cin >> t)) return 0;
  68.     while (t--) {
  69.         cin >> n >> m;
  70.         for (int i = 1; i <= n; ++i) cin >> a[i];
  71.  
  72.         map<int, int> compress;
  73.         int distinct_count = 0;
  74.  
  75.         for (int i = 1; i <= m; ++i) {
  76.             cin >> b[i];
  77.             if (compress.find(b[i]) == compress.end()) {
  78.                 compress[b[i]] = ++distinct_count;
  79.                 memset(P[distinct_count].data, 0, sizeof(P[distinct_count].data));
  80.             }
  81.             P[compress[b[i]]].set_bit(i - 1);
  82.         }
  83.  
  84.         Bitset D; 
  85.  
  86.         static Bitset empty_mask;
  87.         memset(empty_mask.data, 0, sizeof(empty_mask.data));
  88.  
  89.         for (int i = 1; i <= n; ++i) {
  90.             if (compress.find(a[i]) == compress.end()) {
  91.                 D.update(empty_mask); 
  92.             } else {
  93.                 D.update(P[compress[a[i]]]);
  94.             }
  95.         }
  96.  
  97.         cout << D.count() << '\n';
  98.     }
  99.  
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LzLgGd
language:
C++14 (gcc 8.3)
created:
1 day 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!