提出 #49504325

---

ソースコード 拡げる

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

# define int long long
# define For(i, n) for(int i=0; i<n; i++)
# define Fori(i, n) for(int i=1; i<=n; i++)
# define Each(x, v) for(auto x : v)

const int maxn = 4e5;
int tor[maxn+5];
int n, m, k;
int arr[maxn+5];
int window = 0;
int curcnt[maxn+5], cnt[maxn+5];

int bit[maxn+5];
int ls(int x) { return x & (-x); }

void upd(int x, int val){
  for(int i=x; i<=maxn; i+=ls(i)) bit[i] += val;
}

int get(int x){
  int res = 0;
  for(int i=x; i>0; i-=ls(i)) res += bit[i];
  return res;
}

int get(int l, int r){
  return get(r) - get(l-1);
}


bool ok(int l, int r){
  if(r >= l+n) return false;
  if(curcnt[arr[r]] > 0) return true;
  if(curcnt[arr[r]] == 0 && window < m) return true;
  return false;
}

queue<int> pos[maxn+5];
set<int> nums;

signed main(){
  ios_base :: sync_with_stdio(false); 
  cin >> n >> m >> k;
  for(int i=1; i<=n; i++){
    cin >> arr[i];
    pos[arr[i]].push(i);
    nums.insert(arr[i]);
    cnt[arr[i]]++;
  }
  for(int i=n+1; i<=2*n; i++){
    arr[i] = arr[i-n];
    pos[arr[i]].push(i);
  }

  int r = 0;
  for(int l=1; l<=n; l++){
    while(ok(l, r+1)) {
      r++;
      curcnt[arr[r]]++;
      if(curcnt[arr[r]] == 1) window++;
    }
    tor[l] = r;
    curcnt[arr[l]]--;
    if(curcnt[arr[l]] == 0) window--;
  }

  for(int x: nums){
    int p = pos[x].front();
    upd(p, min(cnt[x], k));
  }

  for(int i=1; i<=n; i++){
    int l = i, r = tor[i];
    cout << get(l, r) << "\n";
    int p = pos[arr[i]].front();
    upd(p, -min(cnt[arr[i]], k));
    pos[arr[i]].pop();

    if (!pos[arr[i]].empty()){
      p = pos[arr[i]].front();
      upd(p, min(cnt[arr[i]], k));
    }
  }
}

提出情報

ジャッジ結果