fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class Solution {
  6. public:
  7.     int get(int layer, vector <int> &nums, vector <vector <int> > &precompute, vector <vector <int> > &suff, vector <vector <int> > &pref, vector <vector <int> > &startIdx, vector <int> &lg, int l, int r, int ll, int rr, int init = 0) {
  8.         if (ll >= rr) return nums[ll];
  9.         if (ll + 1 >= rr) return nums[ll] | nums[rr];
  10.         int b = lg[r - l];
  11.         while ((ll - l) / b == (rr - l) / b) { //add binary search or use better indexation
  12.             l += (ll - l) / b * b;
  13.             if (r > l + b) r = l + b;
  14.             b = lg[r - l];
  15.             layer++;
  16.         }
  17.         int ans = init; //block[layer]
  18.         ans |= pref[layer][ll];
  19.         ans |= suff[layer][rr];
  20.         int wl = (ll - l) / b + 1, wr = (rr - l) / b - 1;
  21.         if (wl <= wr) {
  22.             int where = startIdx[layer][l], m = (r - l) / b;
  23.             int w = lg[wr - wl + 1];
  24.             //accurately
  25.             int idx = m * w - (w >= 2 ? ((1 << (w - 1)) - 1) : 0);
  26.             //ans |= precompute[layer][where + idx + (rr / b - 1) - (ll / b + 1)];
  27.             //ans |= precompute[layer][where + ll / b + 1]
  28.             ans |= precompute[layer][where + idx + wl];
  29.             //ans |= precompute[layer][where + rr / b - 1    - t]
  30.             ans |= precompute[layer][where + idx + wr - (1 << w) + 1];
  31.             //cout << ' ' << ans << '\n';
  32.             //if ((rr - l) / b - 1 - (1 << w) + 1 < (ll - l) / b + 1) while (true);
  33.         }
  34.         return ans;
  35.     }
  36.     void build(vector <int> &nums, vector <vector <int> > &precompute, vector <vector <int> > &suff, vector <vector <int> > &pref, vector <vector <int> > &startIdx, vector <int> &lg, vector <int> &ptr, int layer, int l, int r, int init = 0) {
  37.         if (l + 1 >= r) return;
  38.         int b = lg[r - l];
  39.         int m = (r - l) / b;
  40.         startIdx[layer][l] = ptr[layer];
  41.         ptr[layer] += m * b + 2;//
  42.         //if (ptr[layer] >= precompute[layer].size()) cout << "FUCK\n";
  43.         for (int it = l; it < r; it += b) {
  44.             int ll = it, rr = min(r, it + b);
  45.             //startIdx[layer][ll] = ptr[layer]++;
  46.             for (int i = ll; i < rr; ++i) {
  47.                 suff[layer][i] = nums[i];
  48.                 if (i > ll) suff[layer][i] |= suff[layer][i - 1];
  49.                 //precompute[[(it - l) / b * (n / b)] |= nums[i];
  50.             }
  51.             for (int i = rr - 1; i >= ll; --i) {
  52.                 pref[layer][i] = nums[i];
  53.                 if (i + 1 < rr) pref[layer][i] |= pref[layer][i + 1];
  54.             }
  55.         }
  56.         int where = startIdx[layer][l];
  57.         //(n/b)*(n/b+1)/2 [x; y] -> x*(n/b)+y-x
  58.         //[m] [m-1] [m-2] .. [m-2^x] [m-x] ..
  59.         for (int w = 0; (1 << w) <= m; ++w) {
  60.             for (int i = 0; i + (1 << w) - 1 < m; ++i) {
  61.                 int idx = m * w + i - (w >= 2 ? ((1 << (w - 1)) - 1) : 0);
  62.                 //if (idx > m * b + 1) while(true);
  63.                 precompute[layer][where + idx] = (w == 0 ? pref[layer][l + i * b] :
  64.                     precompute[layer][where + m * (w - 1) - (w >= 2 ? ((1 << (w - 2)) - 1) : 0) + i] | 
  65.                     precompute[layer][where + m * (w - 1) - (w >= 2 ? ((1 << (w - 2)) - 1) : 0) + i + (1 << (w - 1))]);
  66.                 //for (int j = i + 1; j < m; ++j) { //geniucos's suggested using sparse-table here but finding indices are tough
  67.                 //    precompute[layer][where + idx + j - i] = precompute[layer][where + idx + (j - i - 1)] | pref[layer][l + j * b];
  68.                 //}
  69.             }
  70.         }
  71.         for (int i = 0; i < m; ++i) {
  72.             if (min(r, l + (i + 1) * b) - (l + i * b) > 1) {
  73.                 build(nums, precompute, suff, pref, startIdx, lg, ptr, layer + 1, l + i * b, min(r, l + (i + 1) * b), init);
  74.             }
  75.         }
  76.     }
  77.     int minimumSubarrayLength(vector<int>& nums, int k) {
  78.         const int D = 5, overhead = 3; //2^(2^D)
  79.         int N = (int)nums.size();
  80.         vector <vector <int> > precompute(D + 1, vector <int>(N *2 + overhead));
  81.         vector <vector <int> > suff(D + 1, vector <int>(N + 1)), pref(D + 1, vector <int>(N + 1));
  82.         vector <vector <int> > startIdx(D + 1, vector <int> (N));
  83.         vector <int> lg(N + 1), ptr(D + 1, 0);
  84.         for (int i = 1; i <= N; ++i) {
  85.             lg[i] = lg[i - 1] + ((1 << (lg[i - 1] + 1)) <= i);
  86.         }
  87.         build(nums, precompute, suff, pref, startIdx, lg, ptr, 0, 0, N, 0);
  88.         //cout << ' ' << get(0, nums, precompute, suff, pref, startIdx, lg, 0, N, 1, N - 1) << '\n';
  89.         //return 0;
  90.         int ans = N + 1;
  91.         for (int i = 0, j = -1; i < N; ++i) {
  92.             if (j < i - 1) j = i - 1;
  93.             for (; j + 1 < N && get(0, nums, precompute, suff, pref, startIdx, lg, 0, N, i, j + 1) < k; ++j);
  94.             if (j + 1 < N && get(0, nums, precompute, suff, pref, startIdx, lg, 0, N, i, j + 1) >= k) ans = min(ans, j + 1 - i + 1);
  95.         }
  96.         return ans > N ? -1 : ans;
  97.     }
  98. } sol;
  99.  
  100. int main() {
  101. 	vector <int> tmp = {2, 1, 8};
  102. 	cout << sol.minimumSubarrayLength(tmp, 10) << '\n';
  103. 	return 0;
  104. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/1yoW91
language:
C++14 (gcc 8.3)
created:
22 days 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!