Submission #1106352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106352		atom	Izbori (COCI22_izbori)	C++17	40 / 110	48 ms	6572 KiB

Main

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 2e5 + 5;
int a[N];
int n;

bool sub12() {
    return (n <= 2000);
}

bool sub3() {
    for (int i = 1; i <= n; ++i)
        if (a[i] > 2) return false;
    return true;
}

template <typename T>
struct Fenwick {
    vector <int> f;
    int n;
    Fenwick(int _n) {
        f.resize(_n + 5);
        n = _n;
    }

    void upd(int x, int val) {
        for (; x <= n; x += x & -x)
            f[x] += val;
    }

    int get(int x) {
        int ans = 0;
        for (; x > 0; x -= x & -x)
            ans += f[x];
        return ans;
    }
};

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    if (sub12()) {
        ll ans = 0;
        for (int l = 1; l <= n; ++l) {
            map <int, int> cnt;
            
            pair <int, int> mx = {0, 0};
            for (int r = l; r <= n; ++r) {
                cnt[a[r]]++;
                if (cnt[a[r]] > mx.second) {
                    mx = make_pair(a[r], cnt[a[r]]);
                }
                if (mx.second > (r - l + 1) / 2) {
                    ++ans;
                }
            }
        }

        cout << ans << "\n";
        return 0;
    }

    if (sub3()) {
        vector <int> prf[3];
        for (int i = 1; i <= 2; ++i)
            prf[i].resize(n + 5);

        for (int i = 1; i <= n; ++i) {
            int x = a[i];
            prf[1][i] = prf[1][i - 1] + (x == 1);
            prf[2][i] = prf[2][i - 1] + (x == 2);
        }

        vector <int> vals[3];
        vals[1].push_back(0);
        vals[2].push_back(0);
        for (int i = 1; i <= n; ++i) {
            vals[1].push_back(2 * prf[1][i] - i);
            vals[2].push_back(2 * prf[2][i] - i);
        }

        sort(vals[1].begin(), vals[1].end());
        vals[1].resize(unique(vals[1].begin(), vals[1].end()) - vals[1].begin());
        sort(vals[2].begin(), vals[2].end());
        vals[2].resize(unique(vals[2].begin(), vals[2].end()) - vals[2].begin());

        auto get = [&] (int x, int t) {
            return (int) (lower_bound(vals[t].begin(), vals[t].end(), x) - vals[t].begin() + 1);
        };

        Fenwick <int> f1(n), f2(n);
        ll ans = 0;
        f1.upd(get(0, 1), 1);
        f2.upd(get(0, 2), 1);
        for (int r = 1; r <= n; ++r) {
            int x1 = get(2 * prf[1][r] - r, 1);
            ans += f1.get(x1 - 1);
            f1.upd(x1, 1);

            int x2 = get(2 * prf[2][r] - r, 2);
            ans += f2.get(x2 - 1);
            f2.upd(x2, 1);
        }

        cout << ans << "\n";
        return 0;
    }
    
    return 0;
}

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