Submission #1204618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204618		LucaIlie	Monochrome Points (JOI20_monochrome)	C++20	0 / 100	0 ms	328 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
int countB[MAX_N + 1], countW[MAX_N + 1];

int main() {
    int n;
    string s;

    cin >> n;
    n *= 2;
    cin >> s;
    for (int i = n - 1; i >= 0; i--) {
        countB[i] = countB[i + 1] + (s[i] == 'B');
        countW[i] = countW[i + 1] + (s[i] == 'W');
    }

    int freeB = 0, freeW = 0;
    queue<int> bs, ws;
    vector<pair<int, int>> pairs;
    for (int i = 0; i < n; i++) {
        freeB += (s[i] == 'B');
        freeW += (s[i] == 'W');
        if (freeB > countW[i + 1] || freeW > countB[i + 1]) {
            freeB -= (s[i] == 'B');
            freeW -= (s[i] == 'W');
            if (s[i] == 'B') {
                pairs.push_back({ws.front(), i});
                ws.pop();
            } else {
                pairs.push_back({bs.front(), i});
                bs.pop();
            }
        } else {
            if (s[i] == 'B')
                bs.push(i);
            else
                ws.push(i);
        }
    }

    int inter = 0;
    for (auto x: pairs) {
        for (auto y: pairs) {
            if (x.second >= y.second)
                continue;

            if (x.second > y.first && x.first < y.first)
                inter++;
        }
    }

    cout << inter << "\n";
}

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