Language: C++

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
#define fout cout << fixed << setprecision(20)
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
struct SegmentTree {
    int n;
    vector<T> node;
    T calc(T a, T b) {
        // return a + b;
        return min(a, b);
        // return max(a, b);
    }
    T e = LINF;
    SegmentTree(vector<T> v) {
        int sz = v.size();
        n = 1;
        while (n < sz) {
            n *= 2;
        }
        node.resize(2 * n - 1, e);
        for (int i = 0; i < sz; i++) {
            node[i + n - 1] = v[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            node[i] = calc(node[2 * i + 1], node[2 * i + 2]);
        }
    }
    SegmentTree(int sz) {
        n = 1;
        while (n < sz) {
            n *= 2;
        }
        node.resize(2 * n - 1, e);
    }
    void update(int x, T val) {
        x = n + x - 1;
        node[x] = val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = calc(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    void add(int x, T val) {
        x = n + x - 1;
        node[x] += val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = calc(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    T query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return e;
        if (a <= l && r <= b) return node[k];
        T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return calc(vl, vr);
    }
    T at(int x) {
        return node[n + x - 1];
    }
};
template <typename T>
vector<T> Dijkstra(int s, vector<vector<pair<int, T>>> &g) {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>>
        que;
    int n = sz(g);
    vector<T> d(n);
    rep(i, n) d[i] = LINF;
    d[s] = 0;
    que.push(make_pair(0LL, s));
    while (!que.empty()) {
        pair<T, int> p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (auto e : g[v]) {
            if (chmin(d[e.first], d[v] + e.second)) {
                que.push(make_pair(d[e.first], e.first));
            }
        }
    }
    return d;
}
int main() {
    int n, k, c;
    cin >> n >> k >> c;
    vector<int> idx;
    string s;
    cin >> s;
    rep(i, n) if (s[i] == 'o') idx.push_back(i + 1);
    if (sz(idx) == 0) return 0;

    vector<vector<pair<int, ll>>> g(n);
    vector<vector<pair<int, ll>>> h(n);
    for (int x : idx) {
        if (x == idx.back()) break;
        g[x].emplace_back(*lower_bound(all(idx), x + c + 1));
        h[*lower_bound(all(idx), x + c + 1)].emplace_back(x, -1);
    }
    g[0].emplace_back(idx[0], -1ll);
    h[n + 1].emplace_back(idx.back(), -1ll);

    auto d = Dijkstra(0, g);
    auto e = Dijkstra(n + 1, h);

    vector<int> ans;
    SegmentTree<ll> left(d), right(e);
    for (int i = 1; i <= n; i++) {
        ll now = -left.query(0, i) - right.query(i + 1, n + 2) + 1;
        ll pre = -d[i] - e[i];
        if (pre >= k && now < k) ans.push_back(i);
    }
    for (int x : ans) cout << x << endl;
}


Compiler output:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/new_allocator.h: In instantiation of 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::pair<int, long long int>; _Args = {int&}; _Tp = std::pair<int, long long int>]':
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<int, long long int>; _Args = {int&}; _Tp = std::pair<int, long long int>; allocator_type = std::allocator<std::pair<int, long long int> >]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/vector.tcc:117:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&}; _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; reference = std::pair<int, long long int>&]'
  117 |             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  118 |                                      std::forward<_Args>(__args)...);
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:132:26:   required from here
  132 |         g[x].emplace_back(*lower_bound(all(idx), x + c + 1));
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/new_allocator.h:191:11: error: no matching function for call to 'std::pair<int, long long int>::pair(int&)'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:913:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<long long int, _U2>::value)), int, long long int>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<long long int, _U2>::value)), int, long long int>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = int; _T2 = long long int]'
  913 |         explicit constexpr pair(pair<_U1, _U2>&& __p)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:913:28: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/new_allocator.h:191:11: note:   mismatched types 'std::pair<_T1, _T2>' and 'int'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:902:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<long long int, _U2>::value)), int, long long int>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<long long int, _U2>::value)), int, long long int>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = int; _T2 = long long int]'
  902 |         constexpr pair(pair<_U1, _U2>&& __p)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:902:19: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/new_allocator.h:191:11: note:   mismatched types 'std::pair<_T1, _T2>' and 'int'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:891:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && (! _ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = int; _T2 = long long int]'
  891 |         explicit constexpr pair(_U1&& __x, _U2&& __y)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:891:28: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_pair.h:881:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && _ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = int; _T2 = long long int]'
  881 |         constexpr pair(_U1&& __x, _U2&& __y)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:881:19: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_pair.h:869:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<long long int, _U2>, std::__not_<std::is_constructible<long long int, const _U1&> >, std::__not_<std::is_convertible<_U2, long long int> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::__not_<std::is_convertible<_U2, _T2> > >::value, bool>::type <anonymous> = _U2; _T1 = int; _T2 = long long int]'
  869 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:869:9: note:   candidate expects at least 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_pair.h:856:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<long long int, _U2>, std::__not_<std::is_constructible<long long int, const _U1&> >, std::is_convertible<_U2, long long int> >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::is_convertible<_U2, _T2> >::value, bool>::type <anonymous> = _U2; _T1 = int; _T2 = long long int]'
  856 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:856:9: note:   candidate expects at least 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_pair.h:843:9: note: candidate: 'template<class _U1, typename std::enable_if<std::__and_<std::__not_<std::is_reference<_Tp> >, std::is_pointer<long long int>, std::is_constructible<int, _U1>, std::__not_<std::is_constructible<int, const _U1&> >, std::__not_<std::is_convertible<_U1, int> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, __zero_as_null_pointer_constant, ...) [with typename std::enable_if<std::__and_<std::__not_<std::is_reference<_U1> >, std::is_pointer<_T2>, std::is_constructible<_T1, _U1>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::__not_<std::is_convertible<_U1, _T1> > >::value, bool>::type <anonymous> = _U1; _T1 = int; _T2 = long long int]'
  843 |         pair(_U1&& __x, __zero_as_null_pointer_constant, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:843:9: note:   candidate expects at least 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_pair.h:830:9: note: candidate: 'template<class _U1, typename std::enable_if<std::__and_<std::__not_<std::is_reference<_Tp> >, std::is_pointer<long long int>, std::is_constructible<int, _U1>, std::__not_<std::is_constructible<int, const _U1&> >, std::is_convertible<_U1, int> >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, __zero_as_null_pointer_constant, ...) [with typename std::enable_if<std::__and_<std::__not_<std::is_reference<_U1> >, std::is_pointer<_T2>, std::is_constructible<_T1, _U1>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::is_convertible<_U1, _T1> >::value, bool>::type <anonymous> = _U1; _T1 = int; _T2 = long long int]'
  830 |         pair(_U1&& __x, __zero_as_null_pointer_constant, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:830:9: note:   candidate expects at least 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_pair.h:789:28: note: candida