Submission #921574

#	Time	Username	Problem	Language	Result	Execution time	Memory
921574		GrandTiger1729	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2011 ms	6616 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
    {
        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;
    };
    long long ans = 0;
    for (int i = 0; i <= n; i++)
    {
        ans = max(ans, solve(i));
    }
    cout << ans << '\n';
    return 0;
}

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