제출 #921588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921588		GrandTiger1729	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	1197 ms	7160 KiB

monochrome

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

struct BIT
{
    int n;
    vector<int> bit;
    BIT(int n_) : n(n_), bit(n + 1) {}
    void add(int i, int u)
    {
        for (; i <= n; i += i & -i)
        {
            bit[i] += u;
        }
    }
    int query(int i)
    {
        int ret = 0;
        for (; i > 0; i -= i & -i)
        {
            ret += bit[i];
        }
        return ret;
    }
    int query(int l, int r)
    {
        return query(r) - query(l);
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    int N = 2 * n;
    string a;
    cin >> a;
    vector<int> b, c;
    for (int i = 0; i < N; i++)
    {
        if (a[i] == 'B')
        {
            b.push_back(i);
        }
        else
        {
            c.push_back(i);
        }
    }
    auto solve = [&](int t) -> long long
    {
        if (t < 0 || t > n)
        {
            return 0;
        }
        vector<pair<int, int>> res;
        for (int i = 0; i < t; i++)
        {
            res.emplace_back(min(b[i], c[n - t + i]), max(b[i], c[n - t + i]));
        }
        for (int i = t; i < n; i++)
        {
            res.emplace_back(min(b[i], c[i - t]), max(b[i], c[i - t]));
        }
        sort(res.begin(), res.end(), [&](pair<int, int> x, pair<int, int> y)
        {
            if (x.second != y.second)
            {
                return x.second < y.second;
            }
            return x.first < y.first;
        });
        long long ret = 0;
        BIT bit(2 * n);
        for (auto &[l, r] : res)
        {
            ret += bit.query(l, r);
            bit.add(l + 1, -1);
            bit.add(r + 1, 1);
        }
        return ret;
    };
    int l = 0, r = n;
    while (l < r - 1)
    {
        int mid = (l + r) / 2;
        if (solve(mid) < solve(mid + 1))
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    long long ans = max(solve(l), solve(l + 1));
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65