SHARE
TWEET

Untitled

a guest Aug 25th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const ll Base1 = 179057;
  6. const ll Base2 = 199909;
  7.  
  8. const ll Mod1 = 998244353;
  9. const ll Mod2 = 1e5 + 7;
  10.  
  11. const int N = 1e5 + 10;
  12.  
  13. vector<ll> S[N];
  14.  
  15. map<ll, vector<int>> Hash;
  16.  
  17. void Inter(vector<ll> &a, vector<ll> &b, ll &Cur)
  18. {
  19.     map<ll, ll> Cnt;
  20.     for (auto i : a) Cnt[i]++;
  21.     for (auto i : b) Cnt[i]++;
  22.  
  23.     for (auto i : Cnt){
  24.         if (i.second < 2) continue;
  25.         Cur = (Cur * Base1 ^ i.first)%Mod1;
  26.         Cur = (Cur * Base2 ^ i.first)%Mod2;
  27.     }
  28. }
  29.  
  30. int main()
  31. {
  32.     ios::sync_with_stdio(0);
  33.     cin.tie(0); cout.tie(0);
  34.  
  35.     int n;  cin >> n;
  36.     int q;  cin >> q;
  37.     for (int i = 1; i <= n; i++)
  38.     {
  39.         int m;  cin >> m;
  40.         for (int j = 0; j < m; j++){
  41.             ll x;   cin >> x;
  42.             S[i].push_back(x);
  43.         }
  44.  
  45.         sort(S[i].begin(), S[i].end());
  46.  
  47.         ll Cur = 0;
  48.         for (ll j : S[i]){
  49.             Cur = (Cur * Base1 ^ j)%Mod1;
  50.             Cur = (Cur * Base2 ^ j)%Mod2;
  51.         }
  52.  
  53.         Hash[Cur].push_back(i);
  54.     }
  55.  
  56.     while(q--)
  57.     {
  58.         int x;  cin >> x;
  59.         int y;  cin >> y;
  60.         int L;  cin >> L;
  61.         int R;  cin >> R;
  62.  
  63.         ll Cur = 0;
  64.         Inter(S[x], S[y], Cur);
  65.  
  66.         cout << upper_bound(Hash[Cur].begin(), Hash[Cur].end(), R) - lower_bound(Hash[Cur].begin(), Hash[Cur].end(), L) << '\n';
  67.     }
  68.  
  69.  
  70.     return 0;
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top