Submission #1003414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003414		Whisper	Izbori (COCI22_izbori)	C++17	40 / 110	3043 ms	21068 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = (n) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

#define MAX             200005
#define BLOCK_SIZE      444
#define off_set         200000

int nArr;
int A[MAX];

vector<int> pos[MAX];


template<class T = vector<int>>
    T unique (T v){
        sort(v.begin(), v.end());
        v.resize(unique(v.begin(), v.end()) - v.begin());
        return v;
    }

template<class T = int>
    T find(T x, const vector<int>& v){
        return (int)(lower_bound(v.begin(), v.end(), x) - v.begin() + 1);
    }

bool hvy[MAX];
int cnt[MAX];
struct custom_hash{
    size_t operator ()(uint64_t x) const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

template<class T = int> struct FenwickTree{
    T *F = nullptr;
    vector<pair<int, int>> opt;
    int n;
    FenwickTree(int _n = 0){
        resize(_n);
    }
    void reset(void){
        fill (F, F + n + 1, T(0));
    }
    void resize(int _n){
        if(F != nullptr) delete[] F;

        this -> n = _n;
        F = new T [n + 5];
        reset();
    }
    void Modify(int p, int val, int c){
        if (c) opt.emplace_back(p, -val);
        for (; p <= n; p += p & (-p)) F[p] += val;
    }
    T Query(int p){
        int res = 0;
        for (; p > 0; p -= p & (-p)) res += F[p];
        return res;
    }
    void rollback(){
        while ((int)opt.size()){
            int p, val; tie(p, val) = opt.back();
            Modify(p, val, 0);
            opt.pop_back();
        }
    }
    int upper_bound(T val){
        int res = 0;
        for (int i = __lg(n); i >= 0; --i) {
            if ((res | MASK(i)) <= n && val >= F[res | MASK(i)]){
                val -= F[res | MASK(i)];
                res |= MASK(i);
            }
        }
        return res + 1;
    }
    int lower_bound(T val){
        int res = 0;
        for (int i = __lg(n); i >= 0; --i){
            if ((res | MASK(i)) <= n && val > F[res | MASK(i)]){
                val -= F[res | MASK(i)];
                res |= MASK(i);
            }
        }
        return res + 1;
    }
};
void process(void){
    cin >> nArr;
    vector<int> comp;
    for (int i = 1; i <= nArr; ++i) cin >> A[i], comp.push_back(A[i]);
    comp = unique(comp);
    for (int i = 1; i <= nArr; ++i) A[i] = find(A[i], comp), cnt[A[i]]++;
    for (int i = 1; i <= nArr; ++i) {
        hvy[i] = (cnt[i] >= BLOCK_SIZE);
    }
    int ans = 0;
    for (int l = 1; l <= nArr; ++l){
        int max_occurence = 0;
        unordered_map<int, int, custom_hash> g;
        for (int r = l; r <= nArr && (r - l + 1 < 2 * BLOCK_SIZE); ++r){
            if(hvy[A[r]]) continue;
            g[A[r]]++;
            maximize(max_occurence, g[A[r]]);
            if (2 * max_occurence > (r - l + 1)) ++ans;
        }
    }

    FenwickTree<int> fen(2 * MAX);
    for (int i = 1; i <= nArr; ++i){
        if (!hvy[i]) continue;
        vector<int> sm(nArr + 5);
        for (int j = 1; j <= nArr; ++j) sm[j] = sm[j - 1] + (A[j] == i ? 1 : -1);
        fen.Modify(off_set, 1, 1);
        for (int j = 1; j <= nArr; ++j){
            ans += fen.Query(sm[j] + off_set - 1);
            fen.Modify(sm[j] + off_set, 1, 1);
        }
        fen.rollback();
    }
    cout << ans;
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
}

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