fork download 
  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 ll MOD = (1ll << 61) - 1; 
  14. const int N = 2e5 + 5; 
  15.  
  16. int n, q; 
  17. int a[N], b[N]; 
  18.  
  19. ll h_val[N]; 
  20. ll sum_h_a[N], sum_h_b[N]; 
  21.  
  22. void precompute() {
  23. 	for (int i = 1; i <= n; i++) h_val[i] = uniform_int_distribution<ll>(0, MOD - 1)(rng); 
  24.  
  25. 	for (int i = 1; i <= n; i++) {
  26. 		sum_h_a[i] = (sum_h_a[i - 1] + h_val[a[i]]) % MOD; 
  27. 		sum_h_b[i] = (sum_h_b[i - 1] + h_val[b[i]]) % MOD; 
  28. 	}
  29. }
  30.  
  31. ll getSumHash(ll sum_h[], int l, int r) {
  32. 	return (sum_h[r] - sum_h[l - 1] + MOD) % MOD; 
  33. }
  34.  
  35. int main() {
  36. 	ios::sync_with_stdio(false); 
  37. 	cin.tie(nullptr); 	
  38. 	cin >> n >> q; 
  39. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  40. 	for (int i = 1; i <= n; i++) cin >> b[i]; 
  41.  
  42. 	precompute();  
  43.  
  44. 	while (q--) {
  45. 		int l1, r1, l2, r2; 
  46. 		cin >> l1 >> r1 >> l2 >> r2; 
  47.  
  48. 		int len_a = r1 - l1 + 1, len_b = r2 - l2 + 1;   
  49.  
  50. 		if (len_a == len_b && getSumHash(sum_h_a, l1, r1) == getSumHash(sum_h_b, l2, r2)) {
  51. 			cout << "Yes" << '\n'; 
  52. 		}
  53. 		else {
  54. 			cout << "No" << '\n'; 
  55. 		}
  56. 	}
  57. }
Success #stdin #stdout 0.01s 7716KB
comments (?)
stdin 
5 4
1 2 3 2 4
2 3 1 4 2
1 3 1 3
1 2 3 5
1 4 2 5
1 5 1 5
stdout 
Yes
No
No
Yes
https://ideone.com/nKJ0uh
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!