fork(1) download
  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
stdin
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
Standard output is empty