Submission #798992

#	Time	Username	Problem	Language	Result	Execution time	Memory
798992		finn__	Chorus (JOI23_chorus)	C++17	100 / 100	1368 ms	32044 KiB

chorus

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

struct linear_fn
{
    int64_t m, t;
    linear_fn(int64_t m, int64_t t) { this->m = m, this->t = t; }
    int64_t operator()(int64_t x) { return m * x + t; }
    bool intersects_earlier(linear_fn const &f, linear_fn const &g)
    {
        return (__int128_t)(f.t - t) * (m - g.m) < (__int128_t)(m - f.m) * (g.t - t);
    }
};

constexpr size_t N = 1000001;

int64_t p[N], j_[N];

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

    size_t n, k;
    string s;
    cin >> n >> k >> s;

    for (size_t i = 1, j = 1, l = 1; i <= n << 1; ++i)
    {
        if (s[i - 1] == 'B')
            j++;
        else
            p[l++] = j;
    }

    for (size_t i = 1; i <= n; ++i)
        j_[i] = max<int64_t>(i, lower_bound(p + 1, p + n + 1, i) - p);

    for (size_t i = 1; i <= n; ++i)
        p[i] += p[i - 1];

    auto cht = [&](int64_t const lambda)
    {
        deque<pair<linear_fn, size_t>> q;
        q.emplace_back(linear_fn(0, -p[j_[1] - 1] + j_[1]), 0);

        for (int64_t i = 1; i <= n; ++i)
        {
            while (q.size() >= 2 && q[0].first(i) >= q[1].first(i))
                q.pop_front();
            int64_t v = q[0].first(i) + p[i] - i - 1 + lambda;
            size_t u = q[0].second + 1;
            if (i == n)
                return make_pair(v, u);
            int64_t const j__ = j_[i + 1];
            linear_fn f(-i, v - p[j__ - 1] + j__ * i + j__ - i);
            while (q.size() >= 2 && q[q.size() - 2].first.intersects_earlier(f, q.back().first))
                q.pop_back();
            q.emplace_back(f, u);
        }
    };

    int64_t a = 0, b = 1LL << 51;
    while (a < b)
    {
        int64_t lambda = (a + b + 1) / 2;
        auto [val, used] = cht(lambda);
        if (used < k)
            b = lambda - 1;
        else
            a = lambda;
    }

    int64_t val = cht(a).first;
    cout << val - (int64_t)k * a << '\n';
}

Compilation message (stderr)

chorus.cpp: In lambda function:
chorus.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int64_t i = 1; i <= n; ++i)
      |                             ~~^~~~
chorus.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (i == n)
      |                 ~~^~~~
chorus.cpp:61:5: warning: control reaches end of non-void function [-Wreturn-type]
   61 |     };
      |     ^

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 26 / 26
• Subtask 5: 13 / 13