fork(1) download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long llo;
  5. #define mp make_pair
  6. #define pb push_back
  7. #define a first 
  8. #define b second
  9. //#define endl '\n'
  10.  
  11. #include "partition.h"
  12.  
  13. #include <vector>
  14. vector<int> aa;
  15. vector<int> bb;
  16. int n;
  17. set<int> xx;
  18. map<int,int> yy;
  19. vector<int> pre[100001];
  20. void init(int nn, vector<int> aaa, vector<int> bbb) {
  21. 	aa=aaa;
  22. 	bb=bbb;
  23. 	n=nn;
  24. 	for(auto j:aa){
  25. 		xx.insert(j);
  26. 	}
  27. 	int ind=0;
  28. 	for(auto j:xx){
  29. 		yy[j]=ind;
  30. 		ind++;
  31. 	}
  32. 	for(int j=0;j<n;j++){
  33. 		pre[yy[aa[j]]].pb(j);
  34. 		aa[j]=yy[aa[j]];
  35. 	}
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42. }
  43. map<pair<int,int>,int> ans2;
  44. int count_partition(int x, int y) {
  45. 	if(xx.find(x)==xx.end()){
  46. 		return 1;
  47. 	}
  48. 	x=yy[x];
  49. 	if(ans2.find({x,y})!=ans2.end()){
  50. 		return ans2[{x,y}];
  51. 	}
  52.  
  53. 	int ans=0;
  54. 	int la=-1;
  55. 	int la2=-1;
  56. 	int co=0;
  57. 	int st=1;
  58. 	while(true){
  59.  
  60. 		int ind=lower_bound(pre[x].begin(),pre[x].end(),la2+bb[y-1])-pre[x].begin();
  61. 		if(ind==pre[x].size()){
  62. 			break;
  63. 		}
  64. 		ind=max(ind,la+y);
  65. 		if(ind>=pre[x].size()){
  66. 			break;
  67. 		}
  68. 		if(pre[x][ind]==n-1){
  69. 			st=0;
  70. 		}
  71. 		ans++;
  72. 		la2=pre[x][ind];
  73. 		la=ind;
  74. 	}
  75. 	ans+=st;
  76. 	ans2[{x,y}]=ans;
  77. 	/*int co=0;
  78. 	int co2=0;
  79. 	int ans=0;
  80. 	for(int i=0;i<n;i++){
  81. 		if(aa[i]==x){
  82. 			co++;
  83. 		}
  84. 		co2++;
  85. 		if(co>=y and co2>=bb[y-1] and aa[i]==x){
  86. 			ans++;
  87. 			co=0;
  88. 			co2=0;
  89. 		}
  90. 		else if(i==n-1){
  91. 			ans++;
  92. 		}
  93. 	}*/
  94. 	/*int ans=(pre[x].size()/y);
  95. 	if(((int)(pre[x].size()%y))>0 or pre[x].back()!=n-1){
  96. 		ans++;
  97. 	}*/
  98.  
  99. 	/*int ans=((int)pre[x].size()+bb[y-1]-1)/bb[y-1];*/
  100.  
  101.  
  102.  
  103.  
  104. 	return ans;
  105. }
  106.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:11:10: fatal error: partition.h: No such file or directory
 #include "partition.h"
          ^~~~~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/9gcEYW
language:
C++14 (gcc 8.3)
created:
3 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!