oj.uz

Submission #1003418

# Submission time Handle Problem Language Result Execution time Memory
1003418 2024-06-20T10:04:13 Z Whisper Izbori (COCI22_izbori) C++17
40 / 110
 3000 ms 15800 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      450
#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 8536 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 5 ms 8248 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 3 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 8536 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 5 ms 8248 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 27 ms 8312 KB Output is correct
8 Correct 4 ms 8284 KB Output is correct
9 Correct 17 ms 8284 KB Output is correct
10 Correct 20 ms 8284 KB Output is correct
11 Correct 28 ms 8300 KB Output is correct
12 Correct 23 ms 8304 KB Output is correct
13 Correct 23 ms 8276 KB Output is correct
14 Correct 18 ms 8308 KB Output is correct
15 Correct 17 ms 8308 KB Output is correct
16 Correct 26 ms 8284 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 13168 KB Output is correct
2 Correct 134 ms 13832 KB Output is correct
3 Correct 80 ms 11256 KB Output is correct
4 Correct 139 ms 13856 KB Output is correct
5 Correct 143 ms 13984 KB Output is correct
6 Correct 152 ms 14116 KB Output is correct
7 Correct 147 ms 14264 KB Output is correct
8 Correct 159 ms 14116 KB Output is correct
9 Correct 152 ms 14264 KB Output is correct
10 Correct 156 ms 14120 KB Output is correct
11 Correct 138 ms 14264 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 5 ms 8248 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 27 ms 8312 KB Output is correct
8 Correct 4 ms 8284 KB Output is correct
9 Correct 17 ms 8284 KB Output is correct
10 Correct 20 ms 8284 KB Output is correct
11 Correct 28 ms 8300 KB Output is correct
12 Correct 23 ms 8304 KB Output is correct
13 Correct 23 ms 8276 KB Output is correct
14 Correct 18 ms 8308 KB Output is correct
15 Correct 17 ms 8308 KB Output is correct
16 Correct 26 ms 8284 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 145 ms 13168 KB Output is correct
19 Correct 134 ms 13832 KB Output is correct
20 Correct 80 ms 11256 KB Output is correct
21 Correct 139 ms 13856 KB Output is correct
22 Correct 143 ms 13984 KB Output is correct
23 Correct 152 ms 14116 KB Output is correct
24 Correct 147 ms 14264 KB Output is correct
25 Correct 159 ms 14116 KB Output is correct
26 Correct 152 ms 14264 KB Output is correct
27 Correct 156 ms 14120 KB Output is correct
28 Correct 138 ms 14264 KB Output is correct
29 Correct 182 ms 15800 KB Output is correct
30 Correct 2214 ms 9028 KB Output is correct
31 Execution timed out 3073 ms 6620 KB Time limit exceeded
32 Halted 0 ms 0 KB -