AtCoder ARC 165 B - Sliding Window Sort 2

B - Sliding Window Sort 2

公式解説 を読んで AC したので紹介。

添字をバグらせ続けてなかなか苦戦したので、誰かの参考になれば。

Submission #45783935 - AtCoder Regular Contest 165

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,k; cin >> n >> k;
  vector<int> p(n);
  REP(i,n) cin >> p[i];

  vector<int> s(n); // s[i] := p[i-1] < p[i] が成り立つ個数の累積和
  REP(i,n-1) s[i+1] = s[i] + (p[i+1] > p[i] ? 1 : 0);
  vector<int> sm(n,1e9); // sm[i] := p[n-k]...p[i] の累積 min
  for(int i = n-k; i < n; i++) sm[i] = min(sm[i-1], p[i]);

  // l-r 間をソートして答えを出力
  auto ans = [&](int l = 0, int r = 0) {
    sort(p.begin()+l,p.begin()+r);
    for(auto v: p) cout << v << " ";
    exit(0);
  };

  REP(l,n) {
    int r = l+k-1;
    if (r >= n) break;
    // p[l] < p[l+1] < p[l+2] < ... < p[r] が成り立つ
    if (s[r] - s[l] == k-1) ans();
  }

  REP(l,n) {
    int r = l+k-1;
    if (r >= n) break;
    if (r < n-k) continue;
    // 条件1: p[l] < p[l+1] < ... < p[n-k] が成り立つ
    bool ok = (s[n-k] - s[l]) == n-k-l;
    // 条件2: p[n-k], p[n-k+1],..., p[r] の最小値は p[n-k-1] より大きい
    ok = ok && p[n-k-1] < sm[r];
    if (ok) ans(l,r+1);
  }

  ans(n-k,n);
  return 0;
}