Lisäykset

#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define N 101010
int fen[N];

void add(int k, int x) {
  for (; k <= N; fen[k] += x, k += k & -k);
}
 
int upto(int k) {
  int s = 0;
  for (; k >= 1; s += fen[k], k -= k & -k);
  return s;
}

int n, m;



int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n>>m;

  int p = 0;
  for (int i = 1; i <= n; i++) {
    int x; cin>>x;

    add(i, x - p);
    p = x;
  }

  for (int qi = 0; qi < m; qi++) {
    int k; cin>>k;

    // bin search endpoints
    // 1 2 2 2 3 5 5 5
    //   ^   ^
    int enp = upto(k);
    int a = 1, b = k+1;
    while (a < b) {
      int mid = a + (b - a) / 2;
      if (upto(mid) == enp) b = mid;
      else a = mid + 1;
    }

    int left_end = a;

    int l = k, r = n+1;
    while (l < r) {
      int mid = l + (r - l) / 2;
      if (upto(mid) != enp) r = mid;
      else l = mid + 1;
    }

    int right_end = l-1;

    int dist = k - left_end;
    
    add(1, 1);
    add(left_end, -1);
    add(right_end - dist, 1);
    add(right_end+1, -1);
  }

  for (int i = 1; i <= n; i++) {
    cout << upto(i) << " ";
  }
  cout<<"\n";
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 3

Verdict: ACCEPTED

Test 4

Group: 1, 3

Verdict: ACCEPTED

Test 5

Group: 1, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED