Submission #502314

#	Time	Username	Problem	Language	Result	Execution time	Memory
502314		tengiz05	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	892 ms	6400 KiB

monochrome

#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    Fenwick(int n) : n(n), a(n) {}
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    T sum(int x) {
        T ans = 0;
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::string s;
    std::cin >> s;
    
    std::vector<int> a, b;
    
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] == 'B') {
            a.push_back(i);
        } else {
            b.push_back(i);
        }
    }
    
    auto solve = [&](int off) {
        std::vector<std::pair<int, int>> v;
        for (int i = 0; i < n; i++) {
            int j = (i + off) % n;
            v.emplace_back(std::minmax(a[i], b[j]));
        }
        std::sort(v.begin(), v.end());
        
        i64 ans = 0;
        Fenwick<int> f(2 * n);
        for (auto [x, y] : v) {
            ans += f.rangeSum(x, y);
            f.add(y, 1);
        }
        return ans;
    };
    
    int l = 0, r = n - 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (solve(m) < solve(m + 1)) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    
    std::cout << solve(l) << "\n";
    
    return 0;
}

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