fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // sample input:-
  6. // 4 
  7. // 1 3 2 5 
  8. // 3 5 3 6 
  9. // 2 
  10. // 1 3 
  11. // 4 6 
  12.  
  13. // answer should be 7
  14.  
  15. int main() {
  16. 	// your code goes here
  17.  
  18. 	int n;
  19. 	cin>> n;
  20.  
  21. 	vector<int> st(n,0), end(n,0);
  22.  
  23. 	// track max;
  24. 	int mx=0;
  25.  
  26. 	for(int i=0; i<n; i++){
  27. 		cin>>st[i];
  28. 	}
  29. 	for(int i=0; i<n; i++){
  30. 		cin>>end[i];
  31. 		mx = max(mx, end[i]);
  32. 	}
  33.  
  34. 	int k;
  35. 	cin>> k;
  36. 	int qs[2], qe[2];
  37.  
  38. 	cin>>qs[0];
  39. 	cin>>qs[1];
  40. 	cin>>qe[0];
  41. 	cin>>qe[1];
  42.  
  43.  
  44.  
  45. 	// <<<<<<<<<<<--------------------------->>>>>>>>>>>>
  46. 	// solution
  47.  
  48. 	// 1 indexed prefix sum that's why (mx+1)
  49. 	vector<int> pre (mx+1, 0);
  50.  
  51.  
  52. 	// update pre with 1 or -1
  53. 	for(int i=0; i<n; i++){
  54.  
  55. 		// from st
  56. 		pre[st[i]] += 1;
  57.  
  58. 		// from end. only skip if it's the last element
  59. 		// because last +1 doesn't exist to put -1
  60. 		if(end[i]!=mx) pre[end[i]+1] += -1;
  61.  
  62.  
  63. 	}
  64.  
  65. 	// calculate pre
  66. 	for(int i=1; i<=mx; i++){
  67. 		pre[i]+=pre[i-1];
  68. 	}
  69.  
  70. 	int ans=0;
  71.  
  72. 	// if(pre[i]>=k) ans+=pre[i];
  73.  
  74. 	// find each hour which is in range of both the queries.
  75. 	// queries might be overlapping. so 
  76. 	vector<int> arr(mx+1, 0);
  77.  
  78. 	for(int i=qs[0]; i<=qe[0]; i++){
  79. 		if(pre[i]>=k) arr[i]++;
  80. 	}
  81. 	for(int i=qs[1]; i<=qe[1]; i++){
  82. 		if(pre[i]>=k) arr[i]++;
  83. 	}
  84.  
  85.  
  86.  
  87. 	// calculate for each one in the range of queries
  88. 	// and add that hour's pre value in ans
  89. 	for(int i=0; i<mx+1; i++){
  90. 		if(arr[i]!=0) ans+=pre[i];
  91. 	}
  92.  
  93.  
  94. 	// for(auto x: pre) cout<<x<<endl;
  95. 	cout<< ans;
  96.  
  97. 	return 0;
  98. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 
1 3 2 5 
3 5 3 6 
2 
1 3 
4 6
stdout
copy 
7
https://ideone.com/5SQmT2
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

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!