fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 100000;
  4. int a[MAXN+1], ans[MAXN+2];
  5. vector<int> ins[MAXN+2], del[MAXN+2];   // we'll do a “sweep‑line” over i
  6.  
  7. void add_range(int L, int R, int val){
  8.     if(L>R) return;
  9.     ins[L].push_back(val);
  10.     del[R+1].push_back(val);
  11. }
  12.  
  13. int main(){
  14.     ios::sync_with_stdio(false);
  15.     cin.tie(nullptr);
  16.  
  17.     int T;
  18.     cin >> T;
  19.     while(T--){
  20.         int n,k;
  21.         cin >> n >> k;
  22.         for(int i=1;i<=n;i++){
  23.             cin >> a[i];
  24.             ans[i] = a[i];           // singleton [i..i] gives nor=a[i]
  25.             ins[i].clear();
  26.             del[i].clear();
  27.         }
  28.         ins[n+1].clear(); del[n+1].clear();
  29.  
  30.         // lst1[j] = last position ≤ r where bit j was 1
  31.         static int lst1[17];
  32.         fill(lst1, lst1+k, 0);
  33.  
  34.         // For each right endpoint r = 1..n:
  35.         for(int r=1;r<=n;r++){
  36.             // Update last-one positions
  37.             for(int j=0;j<k;j++){
  38.                 if(a[r] & (1<<j)) lst1[j] = r;
  39.             }
  40.  
  41.             // Build the O(k) segments by walking backward through
  42.             // the “breakpoints” lst1[j] and lst1[j]-1, as in the editorial.
  43.             // Here we maintain a map from cutoff ℓ0 to a pair (v_even,v_odd),
  44.             // then scan it in order to generate explicit segments [lb,ub].
  45.             map<int, pair<int,int>> mp;
  46.             // Start with the full segment [0..r], whose values depend
  47.             // on parity of r itself; you can check the editorial for
  48.             // exactly how they seed it.
  49.             // ...
  50.             // (cf. LegendStane’s code around L33–L35)
  51.  
  52.             // Now mp is a sorted map whose keys −ℓ0 (breakpoints)
  53.             // carry partial contributions.  We do exactly what L35–L37 do:
  54.             pair<int,int> ad = { (1<<k)-1, 0 };
  55.             if(r%2==1) swap(ad.first, ad.second);
  56.             int ub = r;
  57.             for(auto &it : mp){
  58.                 int lb = -it.first + 1;    // segment from lb..ub
  59.                 auto delta = it.second;    // how bits flip on crossing that breakpoint
  60.                 // schedule range‑updates for parity
  61.                 // even‑ℓ get ad.first, odd‑ℓ get ad.second
  62.                 int lb_even = (lb%2==0 ? lb : lb+1);
  63.                 int lb_odd  = (lb%2==1 ? lb : lb+1);
  64.                 if(lb_even <= ub) add_range(lb_even, ub, ad.first);
  65.                 if(lb_odd  <= ub) add_range(lb_odd,  ub, ad.second);
  66.  
  67.                 // incorporate the delta into ad and shrink ub
  68.                 ad.first  += delta.first;
  69.                 ad.second += delta.second;
  70.                 ub = -it.first; 
  71.             }
  72.             // final segment from ℓ=1..ub
  73.             {
  74.                 int lb=1;
  75.                 int lb_even = (lb%2==0 ? lb : lb+1);
  76.                 int lb_odd  = (lb%2==1 ? lb : lb+1);
  77.                 if(lb_even <= ub) add_range(lb_even, ub, ad.first);
  78.                 if(lb_odd  <= ub) add_range(lb_odd,  ub, ad.second);
  79.             }
  80.         }
  81.  
  82.         // Now do the sweep‑line over i = 1..n, maintaining a multiset of active values
  83.         multiset<int> cur;
  84.         for(int i=1;i<=n;i++){
  85.             for(int v: ins[i]) cur.insert(v);
  86.             for(int v: del[i]) cur.erase(cur.find(v));
  87.             if(!cur.empty())
  88.                 ans[i] = max(ans[i], *cur.rbegin());
  89.         }
  90.  
  91.         // Output
  92.         for(int i=1;i<=n;i++){
  93.             cout << ans[i] << " \n"[i==n];
  94.         }
  95.     }
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 8292KB
comments (?)
stdin 
2
2 2
1 3
5 3
1 7 4 6 2
stdout 
3 3
7 7 7 7 7
https://ideone.com/FOxNFZ
language:
C++ (gcc 8.3)
created:
3 days 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!