Submission #492309

#	Time	Username	Problem	Language	Result	Execution time	Memory
492309		alextodoran	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2084 ms	224236 KiB

monochrome

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N;

string s;

vector <int> v[2];

map <pair <int, int>, int> Fen;

void update (int x, int y) {
    x++; y++;
    for (int i = x; i <= N * 2; i += i & -i) {
        for (int j = y; j <= N * 2; j += j & -j) {
            Fen[{i, j}]++;
        }
    }
}
int query (int x, int y) {
    x++; y++;
    int cnt = 0;
    for (int i = x; i >= 1; i -= i & -i) {
        for (int j = y; j >= 1; j -= j & -j) {
            cnt += Fen[{i, j}];
        }
    }
    return cnt;
}
int intersections (int x, int y) {
    return query(x, y) - query(x, x);
}

ll solve (int offs) {
    Fen.clear();
    vector <pair <int, int>> segments;
    for (int i = 0; i < N; i++) {
        int j = (i + offs) % N;
        segments.push_back(make_pair(v[0][i], v[1][j]));
        if (segments.back().first > segments.back().second) {
            swap(segments.back().first, segments.back().second);
        }
    }
    sort(segments.begin(), segments.end());
    ll cnt = 0;
    for (pair <int, int> p : segments) {
        cnt += intersections(p.first, p.second);
        update(p.first, p.second);
    }
    return cnt;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> s;

    for (int i = 0; i < N * 2; i++) {
        v[(s[i] == 'B')].push_back(i);
    }

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

    cout << solve(l) << "\n";

    return 0;
}

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