Advertisement
Guest User

Untitled

a guest
Aug 25th, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement