Submission #925910

#	Time	Username	Problem	Language	Result	Execution time	Memory
925910		boris_mihov	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	1024 ms	7264 KiB

monochrome

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 400000 + 10;
const int INF  = 2e9;

int n;
int w[MAXN];
int b[MAXN];
char s[MAXN];
std::vector <std::pair <int,int>> v;

struct BIT
{
    int tree[MAXN];
    void reset()
    {
        std::fill(tree, tree + 2 * n + 1, 0);
    }

    void update(int pos, int val)
    {
        for (int idx = pos ; idx <= 2 * n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    int query(int pos)
    {
        int res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }
};

BIT tree;
llong solveFor(int k)
{
    v.clear();
    tree.reset();
    for (int i = 1 ; i <= n ; ++i)
    {
        v.push_back({std::min(w[i], b[(i + k - 1) % n + 1]), std::max(w[i], b[(i + k - 1) % n + 1])});
    }

    llong res = 0;
    std::sort(v.begin(), v.end());
    for (int i = n - 1 ; i >= 0 ; --i)
    {
        res += tree.query(v[i].second);
        tree.update(v[i].first + 1, + 1);
        tree.update(v[i].second, -1);
    }

    return res;
}

void solve()
{
    int cntW = 1;
    int cntB = 1;
    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        if (s[i] == s[1]) w[cntW++] = i;
        else b[cntB++] = i;
    }

    int l = 0, r = n - 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (solveFor(mid) - solveFor(mid - 1) >= 0) l = mid;
        else r = mid;
    }

    llong res = std::max(solveFor(0), solveFor(n - 1));
    std::cout << std::max(res, solveFor(l)) << '\n';
}

void input()
{
    std::cin >> n;
    std::cin >> s + 1;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'void input()':
monochrome.cpp:96:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |     std::cin >> s + 1;
      |                 ~~^~~

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