Submission #492310

#	Time	Username	Problem	Language	Result	Execution time	Memory
492310		alextodoran	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	977 ms	8072 KiB

monochrome

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

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N;

string s;

vector <int> v[2];

int Fen[N_MAX * 2 + 2];

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

ll solve (int offs) {
    for (int i = 1; i <= N * 2; i++) {
        Fen[i] = 0;
    }
    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.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: 65 / 65