#include using namespace std; #define all(hoge) (hoge).begin(), (hoge).end() #define en '\n' using ll = long long; using ull = unsigned long long; #define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i) #define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i) #define REP(i, n) rep(i, 0, n) #define REP2(i, n) rep2(i, 0, n) template using vec = vector; template using vvec = vector>; typedef pair P; using tp = tuple; constexpr long long INF = 1LL << 60; constexpr int INF_INT = 1 << 25; constexpr long long MOD = (ll) 1e9 + 7; //constexpr long long MOD = 998244353LL; using ld = long double; static const ld pi = 3.141592653589793L; using Array = vector; using Matrix = vector; /* #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") */ template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template class SegmentTree { private: T e; F op; ll n; vector dat; public: SegmentTree(F f, T _e, vector v) : op(f), e(_e) { int _n = v.size(); n = 1; while(n < _n) n *= 2; dat.resize(2 * n - 1, e); REP(i, _n) dat[n + i - 1] = v[i]; for(int i = n - 2; i >= 0; i--) dat[i] = op(dat[i * 2 + 1], dat[i * 2 + 2]); } SegmentTree(F f, T _e, int _n) : op(f), e(_e) { n = 1; while(n < _n) n *= 2; dat.resize(2 * n - 1, e); for(int i = n - 2; i >= 0; i--) dat[i] = op(dat[i * 2 + 1], dat[i * 2 + 2]); } void update(int i, T x) { i += n - 1; dat[i] = x; while(i > 0) { i = (i - 1) / 2; dat[i] = op(dat[i * 2 + 1], dat[i * 2 + 2]); } } T get(int i) { i += n - 1; return dat[i]; } T query(int l, int r) { //[l,r)でのクエリ処理 T left = e, right = e; l += n - 1; r += n - 1; while(l < r) { if((l & 1) == 0) left = op(left, dat[l]); if((r & 1) == 0) right = op(dat[r - 1], right); l = l / 2; r = (r - 1) / 2; } return op(left, right); } }; void solve() { ll n,k; string s; cin>>n>>k>>s; vec grundy(n+k + 1,0); vec

vs; REP(i,k+1) vs.push_back({0,i}); vs[0].first = k; using S=P; S id={INF,INF}; auto op = [](S a, S b) {return min(a,b); }; SegmentTree seg(op,id,vs); REP2(i,n-1){ if(s[i]=='o'){ auto [con,mi] = seg.query(0,k+1); grundy[i] = mi; } seg.update(grundy[i],{seg.get(grundy[i]).first + 1,grundy[i]}); ll t = grundy[i + k]; seg.update(t,{seg.get(t).first-1,t}); } ll ans=0; rep(i,1,k+1){ if(grundy[i])continue; if(grundy[i-1]) ans = i; } cout<> t; REP(i, t - 1) { solve(); }*/ solve(); return 0; }