Submission #1199609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199609		badge881	Monochrome Points (JOI20_monochrome)	C++20	100 / 100	1544 ms	11248 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

const int SIZE = 2e5 + 5;
string S;
int ps[2][SIZE];
int tree[2 * SIZE];

void modify(int pos, int val)
{
    for (; pos < 2 * SIZE; pos += (pos & -pos))
        tree[pos] += val;
    return;
}

int query(int pos)
{
    int ret = 0;
    for (; pos; pos -= (pos & -pos))
        ret += tree[pos];
    return ret;
}

long long vv[SIZE];

long long eval(int x, int N)
{
    x %= N;
    if (vv[x])
        return vv[x];
    for (int i = 0; i < 2 * N; i++)
    {
        tree[i] = 0;
    }
    long long ans = 0;
    vector<pair<int, int>> seg;
    for (int i = 0; i < N; i++)
    {
        seg.push_back({ps[0][i], ps[1][(i + x) % N]});
        seg.push_back({ps[1][(i + x) % N], ps[0][i]});
    }
    sort(seg.begin(), seg.end());
    for (auto i : seg)
        if (i.second > i.first)
            ans += query(i.second),
                modify(i.second, 1);
        else
            modify(i.first, -1);
    return vv[x] = ans;
}

int main()
{
    int N;
    S.resize(2 * SIZE);
    scanf("%d\n%s", &N, &S[0]);
    int ptr[2] = {0, 0};
    for (int i = 0; i < 2 * N; i++)
        ps[S[i] == 'W'][ptr[S[i] == 'W']++] = i;
    long long water_line = eval(0, N);
    if (eval(1, N) >= water_line)
    {
        int L = 0, R = N - 1, M;
        while (L != R)
        {
            M = (L + R + 1) / 2;
            if (eval(M, N) < water_line)
                R = M - 1;
            else
                L = M;
        }
        L = 0;
        while (L != R)
        {
            M = (L + R) / 2;
            if (eval(M, N) < eval(M + 1, N))
                L = M + 1;
            else
                R = M;
        }
        printf("%lld\n", eval(L, N));
    }
    else
    {
        int L = 0, R = N - 1, M;
        while (L != R)
        {
            M = (L + R) / 2;
            if (eval(M, N) > water_line)
                R = M;
            else
                L = M + 1;
        }
        R = N;
        while (L != R)
        {
            M = (L + R) / 2;
            if (eval(M, N) < eval(M + 1, N))
                L = M + 1;
            else
                R = M;
        }
        printf("%lld", eval(L, N));
    }
    return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d\n%s", &N, &S[0]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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