fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m;
  5. vector<int> a;
  6.  
  7. #define sz(x) ((int)(x).size())
  8.  
  9. const int MAX_E = 17, MAX_M = 1e5 + 3;
  10. int freq[MAX_M];
  11. vector<int> freqMod[MAX_E + 1], ind[MAX_M];
  12.  
  13. vector<int> S, F;
  14. int minF, sIdx, sIdxSol, sIdxSolutionMin, sumF;
  15.  
  16. int jump(int x)
  17. {
  18.     return (1<<x);
  19. }
  20.  
  21. const int MOD = 1000000007;
  22. int add(int x, int y)
  23. {
  24.     x += y;
  25.     x -= MOD * (x >= MOD);
  26.     return x;
  27. }
  28.  
  29. int sumVec(const vector<int> &v)
  30. {
  31.     int ret = 0;
  32.     for (int x : v)
  33.         ret = add(ret, x);
  34.     return ret;
  35. }
  36.  
  37. int minVec(const vector<int> &v)
  38. {
  39.     int ret = INT_MAX;
  40.     for (int x : v)
  41.         ret = min(ret, x);
  42.     return ret;
  43. }
  44.  
  45.  
  46. void clear()
  47. {
  48.     for (int i = 0; i < sz(a); ++i)
  49.     {
  50.         int x = a[i];
  51.         freq[x]--;
  52.         if (x <= MAX_E)
  53.             freqMod[x][i%jump(x)]--;
  54.         ind[x].clear();
  55.     }
  56.     a.clear();
  57. }
  58.  
  59. vector<int> getDiff(const vector<int> &v, int k)
  60. {
  61.     vector<int> ans(k);
  62.     vector<int> modPos(MAX_E + 1, sz(v));
  63.     for (int i = 0; i < sz(v); ++i)
  64.         modPos[v[i]] = min(modPos[v[i]], i);
  65.     for (int x = 1; x <= MAX_E; ++x)
  66.     {
  67.         int curMod = modPos[x];
  68.         if (curMod == sz(v))
  69.             continue;
  70.         int j = jump(x);
  71.         for (int shift = 0; shift < k; )
  72.         {
  73.             if (curMod < 0)
  74.                 curMod += j;
  75.             if (curMod >= n)
  76.             {
  77.                 int minus = curMod - (n - 1);
  78.                 curMod -= minus;
  79.                 shift += minus;
  80.                 continue;
  81.             }
  82.             int freqHere = ((n - 1 - curMod) / j) + 1;
  83.             ans[shift] += freqHere - freqMod[x][curMod];
  84.             ++shift;
  85.             curMod--;
  86.         }
  87.     }
  88.     return ans;
  89. }
  90.  
  91. void calcS()
  92. {
  93.     sIdx = 1;
  94.     S.clear();
  95.     S.push_back(1);
  96.     while(sz(S) < n - 1) {
  97.         int T = sz(S);
  98.         sIdx++;
  99.         S.push_back(sIdx);
  100.         for (int i = 0; i < T; ++i)
  101.         {
  102.             int x = S[i];
  103.             S.push_back(x);
  104.         }
  105.     }
  106.     vector<int> ans = getDiff(S, sz(S) - sz(a) + 1);
  107.     sIdxSol = sumVec(ans);
  108.     sIdxSolutionMin = minVec(ans);
  109. }
  110.  
  111. void calcF()
  112. {
  113.     vector<int> temp(S.begin() + sz(S) - n + 1, S.end());
  114.     F = getDiff(temp, n);
  115.     sumF = sumVec(F);
  116.     minF = minVec(F);
  117. }
  118.  
  119. int solveSum(int cur)
  120. {
  121.     return add(sumF, n - freq[cur]);
  122. }
  123.  
  124. int sum(int mx)
  125. {
  126.     int ret = sIdxSol;
  127.     for (int cur = sIdx + 1; cur <= mx; ++cur)
  128.         ret = add(add(ret, ret), solveSum(cur));
  129.     return ret;
  130. }
  131.  
  132. int solveMin(int cur) {
  133.     int ret = minF + 1;
  134.     for (int i : ind[cur])
  135.     {
  136.         ret = min(ret, F[n - i - 1]);
  137.     }
  138.     return ret;
  139. }
  140.  
  141. int mn(int mx)
  142. {
  143.     int ret = sIdxSolutionMin;
  144.     for (int cur = sIdx + 1; cur <= mx; ++cur)
  145.         ret = min(ret, solveMin(cur));
  146.     return ret;
  147. }
  148.  
  149. void myMain()
  150. {
  151.     a.resize(n);
  152.     for (int i = 0; i < n; ++i)
  153.         scanf("%d", &a[i]);
  154.  
  155.     for (int i = 0; i < sz(a); ++i)
  156.     {
  157.         freq[a[i]]++;
  158.         if (a[i] <= MAX_E)
  159.             freqMod[a[i]][i%jump(a[i])]++;
  160.         ind[a[i]].push_back(i);
  161.     }
  162.  
  163.     calcS();
  164.     calcF();
  165.     printf("%d %d\n", mn(m), sum(m));
  166.     clear();
  167. }
  168.  
  169. int main()
  170. {
  171.     freopen("input.txt", "r", stdin);
  172.  
  173.     S.reserve(1<<MAX_E);
  174.     for (int x = 0; x <= MAX_E; ++x)
  175.         freqMod[x].resize(jump(x));
  176.  
  177.     while(scanf("%d %d", &n, &m) != EOF)
  178.         myMain();
  179.  
  180. }
Success #stdin #stdout 0s 6716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AirWlG
language:
C++14 (gcc 8.3)
created:
3 years 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!