oj.uz

Submission #1003416

# Submission time Handle Problem Language Result Execution time Memory
1003416 2024-06-20T10:03:33 Z Whisper Izbori (COCI22_izbori) C++17
40 / 110
 3000 ms 15668 KB 
#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      400
#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);
    }
    long long 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<long long> 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 24 ms 8324 KB Output is correct
8 Correct 4 ms 8280 KB Output is correct
9 Correct 16 ms 8148 KB Output is correct
10 Correct 20 ms 8280 KB Output is correct
11 Correct 20 ms 8312 KB Output is correct
12 Correct 22 ms 8284 KB Output is correct
13 Correct 18 ms 8304 KB Output is correct
14 Correct 16 ms 8276 KB Output is correct
15 Correct 17 ms 8280 KB Output is correct
16 Correct 22 ms 8296 KB Output is correct
17 Correct 4 ms 8268 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 13144 KB Output is correct
2 Correct 110 ms 13864 KB Output is correct
3 Correct 70 ms 11332 KB Output is correct
4 Correct 115 ms 13936 KB Output is correct
5 Correct 114 ms 14052 KB Output is correct
6 Correct 122 ms 14264 KB Output is correct
7 Correct 130 ms 14264 KB Output is correct
8 Correct 131 ms 14272 KB Output is correct
9 Correct 124 ms 14108 KB Output is correct
10 Correct 120 ms 14116 KB Output is correct
11 Correct 127 ms 14264 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 24 ms 8324 KB Output is correct
8 Correct 4 ms 8280 KB Output is correct
9 Correct 16 ms 8148 KB Output is correct
10 Correct 20 ms 8280 KB Output is correct
11 Correct 20 ms 8312 KB Output is correct
12 Correct 22 ms 8284 KB Output is correct
13 Correct 18 ms 8304 KB Output is correct
14 Correct 16 ms 8276 KB Output is correct
15 Correct 17 ms 8280 KB Output is correct
16 Correct 22 ms 8296 KB Output is correct
17 Correct 4 ms 8268 KB Output is correct
18 Correct 95 ms 13144 KB Output is correct
19 Correct 110 ms 13864 KB Output is correct
20 Correct 70 ms 11332 KB Output is correct
21 Correct 115 ms 13936 KB Output is correct
22 Correct 114 ms 14052 KB Output is correct
23 Correct 122 ms 14264 KB Output is correct
24 Correct 130 ms 14264 KB Output is correct
25 Correct 131 ms 14272 KB Output is correct
26 Correct 124 ms 14108 KB Output is correct
27 Correct 120 ms 14116 KB Output is correct
28 Correct 127 ms 14264 KB Output is correct
29 Correct 134 ms 15668 KB Output is correct
30 Correct 1798 ms 9080 KB Output is correct
31 Execution timed out 3069 ms 6620 KB Time limit exceeded
32 Halted 0 ms 0 KB -