Submission #1106446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106446		atom	Izbori (COCI22_izbori)	C++17	40 / 110	427 ms	8644 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;
    const int B = 450;
    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("in2", "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;
        }
     
        vector <int> vals;
        for (int i = 1; i <= n; ++i)
            vals.push_back(a[i]);
     
        sort(vals.begin(), vals.end());
        vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
     
        int sz = (int) vals.size();
        vector <int> cnt(sz, 0);
        for (int i = 1; i <= n; ++i) {
            a[i] = (int) (lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
            cnt[a[i]]++;
        }
     
        vector <bool> heavy(sz, false);
        for (int i = 0; i < sz; ++i) {
            if (cnt[i] >= B)
                heavy[i] = true;
        }
     
        ll ans = 0;
        // processing light queries: all elements appear less than sqrt(n)
        cnt.clear();
        for (int i = 1; i <= n; ++i) {
            int mx = 0;
            for (int j = i; j <= n && (j - i + 1) / 2 < B; ++j) {
                if (!heavy[a[j]]) {
                    cnt[a[j]]++;
                    if (cnt[a[j]] > mx) mx = cnt[a[j]];
                    if (mx > (j - i + 1) / 2) ++ans;
                }
            }
     
            for (int j = i; j <= n && (j - i + 1) / 2 < B; ++j)
                if (!heavy[a[j]]) cnt[a[j]]--;
        }
     
        // processing heavy queries: all elements appear at least sqrt(n)
        for (int x = 0; x < sz; ++x) {
            if (heavy[x]) {
                auto get = [&] (int _x) { return _x + n; };
     
                vector <int> prf(n + 1);
                for (int i = 1; i <= n; ++i)
                    prf[i] = prf[i - 1] + (a[i] == x? 1 : -1);
     
                vector <int> f(2 * n, 0);
                f[get(0)]++;
                ll sum = 0;
                for (int i = 1; i <= n; ++i) {
                    if (a[i] == x)
                        sum += cnt[get(prf[i] - 1)];
                    else    
                        sum -= cnt[get(prf[i])];
                    ans += sum;
                    cnt[get(prf[i])]++;
                }
            }
        }
     
        cout << ans << "\n";
     
        
        return 0;
    }

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