fork download 
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp> // Common file
  3. //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4.  
  5. using namespace std;
  6. //using namespace __gnu_pbds;
  7. //typedef tree< pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
  8. //ordered_set;
  9. int dx[] = {0, 1, 0, -1};
  10. int dy[] = {-1, 0, 1, 0};
  11. #define X first
  12. #define Y second
  13. #define int long long
  14. const int N = (int)2e5 + 10;
  15. const int MOD = 1000000007;
  16.  
  17.  
  18. void solve(){
  19.     int X; cin >> X;
  20.     int n; cin >> n;
  21.     vector<int> a(n);
  22.     for(auto & x: a)
  23.         cin >> x;
  24.     int m; cin >> m;
  25.     vector<int> b(m);
  26.     for(auto & x: b)
  27.         cin >> x;
  28.     if(n == 1){
  29.         int ans = 0;
  30.         for(auto & x: b){
  31.             int differ = x - a[0];
  32.             if( abs(differ) <= X )
  33.                 ans++;
  34.         }
  35.         cout << ans << '\n';
  36.         return;
  37.     }
  38.     vector<int> diff(n + m - 1), org(n + m + 1);
  39.     for(int i = 0; i < n; ++i)
  40.         org[i] = a[i];
  41.     org[n] = INT_MIN;
  42.     for(int i = n + 1, j = 0; j < m; ++i, ++j)
  43.         org[i] = b[j];
  44.     int id = 0;
  45.     for(int i = 0; i + 1 < n; ++i){
  46.         diff[id++] = a[i + 1] - a[i];
  47.     }
  48.     diff[id++] = INT_MIN;
  49.     for(int i = 0; i + 1 < m; ++i){
  50.         diff[id++] = b[i + 1] - b[i];
  51.     }
  52.     int sz = diff.size();
  53.     vector<int> pi(sz);
  54.     pi[0] = 0;
  55.     for(int i = 1; i < sz; ++i){
  56.         int j = pi[i - 1];
  57.         while(j > 0 and diff[i] != diff[j] ){
  58.             j = pi[j - 1];
  59.         }
  60.         if( diff[i] == diff[j])
  61.             j++;
  62.         pi[i] = j;
  63.     }
  64.     int ans = 0;
  65.     for(int i = n; i < sz; ++i){
  66.         if( pi[i] == n - 1){
  67.             int currid = i - n + 3;
  68.             int x =  org[currid] - a[0];
  69.             x = abs(x);
  70.             if(x <= X)
  71.                 ans++;
  72.         }
  73.     }
  74.     cout << ans << '\n';
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81. }
  82.  
  83. int32_t main(){
  84.     ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); 
  85.     int t; cin >> t;
  86.     while(t--)
  87.         solve();
  88.     return 0;
  89. }
Runtime error #stdin #stdout #stderr 0s 4240KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/Cb7RRa
language:
C++14 (gcc 8.3)
created:
4 years 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!