Submission #1266627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266627		canhnam357	Izbori (COCI22_izbori)	C++20	110 / 110	369 ms	8972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
long long f(int l, int r) {
    return 1LL * (l + r) * (r - l + 1) / 2;
}
#define N 200'005
int bit[2 * N]{}, mark[2 * N]{}, timer = 0;
void update(int pos, int val) {
    while (pos < 2 * N) {
        if (mark[pos] != timer) {
            mark[pos] = timer;
            bit[pos] = 0;
        }
        bit[pos] += val;
        pos += pos & -pos;
    }
}
int get(int pos) {
    int ans = 0;
    while (pos > 0) {
        if (mark[pos] != timer) {
            mark[pos] = timer;
            bit[pos] = 0;
        }
        ans += bit[pos];
        pos -= pos & -pos;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    auto cc = a;
    sort(cc.begin(), cc.end());
    cc.erase(unique(cc.begin(), cc.end()), cc.end());
    for (int &i : a) {
        i = lower_bound(cc.begin(), cc.end(), i) - cc.begin();
    }
    int m = cc.size();
    const int B = 1000;
    vector<vector<int>> pos(m);
    for (int i = 0; i < n; i++) {
        pos[a[i]].push_back(i);
    }
    long long ans = n;
    for (int i = 0; i < m; i++) {
        timer++;
        if (pos[i].size() > B) {
            int sum = N;
            update(sum, 1);
            for (int j : a) {
                if (j == i) sum++;
                else sum--;
                ans += get(sum - 1);
                update(sum, 1);
            }
            ans -= pos[i].size();
        }
        else {
            for (int l = 0; l < pos[i].size(); l++) {
                for (int r = l + 1; r < pos[i].size(); r++) {
                    int bad = pos[i][r] - pos[i][l] - r + l;
                    if (bad >= r - l + 1) continue;
                    int lb = 0, rb = r - l - bad;
                    int le = (l ? pos[i][l] - pos[i][l - 1] - 1 : pos[i][l]);
                    int ri = (r + 1 == pos[i].size() ? n - 1 - pos[i][r] : pos[i][r + 1] - pos[i][r] - 1);
                    le = min(le, rb);
                    ri = min(ri, rb);
                    ans += le + 1;
                    if (rb <= ri) ans += f(rb - le, rb);
                    else if (rb - le >= ri) ans += ri * (le + 1);
                    else {
                        ans += f(rb - le, ri);
                        ans += (rb - ri) * ri;
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 70 / 70