oj.uz

Submission #921572

# Submission time Handle Problem Language Result Execution time Memory
921572 2024-02-04T06:53:39 Z GrandTiger1729 Monochrome Points (JOI20_monochrome) C++17
0 / 100
 1 ms 348 KB 
#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;
    };
    int i = 0;
    while (i < n && b[i] < c[n - 1 - i])
    {
        i++;
    }
    long long ans = solve(i);
    if (i > 0)
    {
        ans = max(ans, solve(i - 1));
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -