fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 100010
  4. #define pii pair<int,int>
  5. #define mp make_pair
  6. #define F first
  7. #define S second
  8. int a[maxn], b[maxn], posa[maxn], posb[maxn];
  9.  
  10. int p[maxn], q[maxn];
  11. bool pt;
  12. pii u[maxn];
  13. int dp[maxn], prev[maxn];
  14. struct node{
  15. 	int lft;
  16. 	int rgt;
  17. 	int val; 
  18. 	node(){
  19. 		lft= 0;
  20. 		rgt= 0;
  21. 		val= 0;
  22. 	}
  23. };
  24. #define SN 20000007
  25. node segtree[SN];
  26.  
  27. int curr = 0;
  28. void upd (int &n, int L, int R, int ind, int res){
  29. 	if (L>R or L>ind or ind>R) return;
  30. 	if(!n){
  31. 		n = ++curr;
  32. 	}
  33. 	++segtree[n].val;
  34. 	if(L < R){
  35. 		int mid= (L+R)/2;
  36. 		if (ind<=mid){
  37. 			upd(segtree[n].lft, L, mid, ind, res);
  38. 		}
  39. 		else{
  40. 			upd (segtree[n].rgt, mid+1, R, ind, res);
  41. 		}
  42. 	}
  43. }
  44.  
  45. int query (int n, int L, int R, int S, int E){
  46. 	if (L>R or L>E or S>R or !n) return 0;
  47. 	if (L>=S and R<=E) {
  48. 		return segtree[n].val;
  49. 	}
  50. 	int mid= (L+R)/2;
  51. 	return query(segtree[n].lft, L, mid, S, E)+ query(segtree[n].rgt, mid+1, R, S, E);
  52. }
  53.  
  54. int bit[maxn];
  55. int N, n;
  56.  
  57. void treeupd (int x, int y){
  58. 	while (x<N){
  59. 		upd(bit[x], 1, n, y, 1);
  60. 		x+=x&(-x);
  61. 	}
  62. }
  63.  
  64. int treequery  (int x, int y1, int y2){
  65. 	if (x==0 or y1==0 or y2==0 or y1>y2) return 0;
  66. 	int ans= 0;
  67. 	while (x){
  68. 		ans+=query(bit[x], 1, n, y1, y2);
  69. 		x-=x&(-x);
  70. 	}
  71. 	return ans;
  72. }
  73.  
  74. int check (int x){
  75. 	if (x<=0 or x>n) return 0;
  76. 	return 1;
  77. }
  78.  
  79. int ask (int x1, int x2, int y1, int y2){
  80. 	if (x1>x2 or y1>y2 or !check(x1) or !check(x2) or !check(y1) or !check(y2)) return 0;
  81. 	return treequery(x2, y1, y2) - treequery(x1-1, y1, y2);
  82. }
  83.  
  84. int ans[maxn];
  85.  
  86. int main(){
  87. 	freopen ("friendcross.in", "r", stdin);
  88.  	freopen ("friendcross.out", "w", stdout);
  89. 	int k;
  90. 	cin>>n>>k;
  91. 	for (int i=1; i<=n; i++) {
  92. 		cin>>a[i];
  93. 		posa[a[i]]= i;
  94. 	}
  95. 	for (int i=1; i<=n; i++) {
  96. 		cin>>b[i];	
  97. 		posb[b[i]]= i;
  98. 	}
  99. 	N= n+5;
  100. 	for (int i=1; i<=n; i++){
  101. 		if (i+k+1>n) continue;
  102. 		int t= i+k+1;
  103. 		treeupd(posa[i], posb[i]);
  104. 		ans[i+k+1]= ask(1, posa[t], posb[t], n) + ask(posa[t], n, 1, posb[t]) - ask(posa[t], posa[t], posb[t], posb[t]);
  105. 	}
  106.  
  107. 	long long int anss= 0LL;
  108. 	for (int i=1; i<=n; i++) anss+=ans[i];
  109. 	cout<<anss<<endl;	
  110. }
Success #stdin #stdout 0.05s 254272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/sfKpb4
language:
C++ (gcc 8.3)
created:
7 years 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!