fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());   
  12.  
  13. const int N = 2e5 + 5; 
  14.  
  15. int n, q;  
  16. int a[N], b[N];   
  17.  
  18. map<int, ll> h_val;   
  19. ll pref_xor_a[N], pref_xor_b[N];  
  20.  
  21. void precompute() {
  22. 	for (int i = 1; i <= n; i++) {
  23. 		if (!h_val.count(a[i])) h_val[a[i]] = rng(); 
  24. 		if (!h_val.count(b[i])) h_val[b[i]] = rng();  
  25. 	}
  26.  
  27. 	map<int, bool> seen; 
  28. 	for (int i = 1; i <= n; i++) {
  29. 		pref_xor_a[i] = pref_xor_a[i - 1]; 
  30. 		if (!seen.count(a[i])) pref_xor_a[i] ^= h_val[a[i]]; 
  31. 		seen[a[i]] = true; 
  32. 	}
  33.  
  34. 	seen.clear(); 
  35. 	for (int i = 1; i <= n; i++) {
  36. 		pref_xor_b[i] = pref_xor_b[i - 1]; 
  37. 		if (!seen.count(b[i])) pref_xor_b[i] ^= h_val[b[i]];   
  38. 		seen[b[i]] = true; 
  39. 	}
  40. }
  41.  
  42. int main() {
  43. 	ios::sync_with_stdio(false); 
  44. 	cin.tie(nullptr); 	
  45. 	cin >> n; 
  46. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  47. 	for (int i = 1; i <= n; i++) cin >> b[i]; 
  48.  
  49. 	precompute();  
  50.  
  51. 	cin >> q;
  52.  
  53. 	while (q--) {
  54. 		int x, y; 
  55. 		cin >> x >> y; 
  56.  
  57. 		if (pref_xor_a[x] == pref_xor_b[y]) {
  58. 			cout << "Yes" << '\n'; 
  59. 		}
  60. 		else {
  61. 			cout << "No" << '\n'; 
  62. 		}
  63. 	}
  64. }
Success #stdin #stdout 0.01s 5636KB
comments (?)
stdin
copy 
5
1 2 3 4 5
1 2 2 4 3
7
1 1
2 2
2 3
3 3
4 4
4 5
5 5
stdout
copy 
Yes
Yes
Yes
No
No
Yes
No
https://ideone.com/x4tyk0
language:
C++14 (gcc 8.3)
created:
333 days ago
visibility:
secret

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!