oj.uz

Submission #1003414

# Submission time Handle Problem Language Result Execution time Memory
1003414 2024-06-20T10:01:35 Z Whisper Izbori (COCI22_izbori) C++17
40 / 110
 3000 ms 21068 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      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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 4 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 6 ms 8284 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 4 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 6 ms 8284 KB Output is correct
7 Correct 26 ms 8244 KB Output is correct
8 Correct 4 ms 8280 KB Output is correct
9 Correct 28 ms 8332 KB Output is correct
10 Correct 23 ms 8328 KB Output is correct
11 Correct 23 ms 8252 KB Output is correct
12 Correct 23 ms 8280 KB Output is correct
13 Correct 18 ms 8332 KB Output is correct
14 Correct 23 ms 8284 KB Output is correct
15 Correct 23 ms 8328 KB Output is correct
16 Correct 23 ms 8280 KB Output is correct
17 Correct 7 ms 8280 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 17752 KB Output is correct
2 Correct 263 ms 19052 KB Output is correct
3 Correct 129 ms 14004 KB Output is correct
4 Correct 233 ms 19256 KB Output is correct
5 Correct 248 ms 19304 KB Output is correct
6 Correct 268 ms 19616 KB Output is correct
7 Correct 264 ms 19624 KB Output is correct
8 Correct 272 ms 19620 KB Output is correct
9 Correct 249 ms 19628 KB Output is correct
10 Correct 233 ms 19504 KB Output is correct
11 Correct 232 ms 19620 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 4 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 6 ms 8284 KB Output is correct
7 Correct 26 ms 8244 KB Output is correct
8 Correct 4 ms 8280 KB Output is correct
9 Correct 28 ms 8332 KB Output is correct
10 Correct 23 ms 8328 KB Output is correct
11 Correct 23 ms 8252 KB Output is correct
12 Correct 23 ms 8280 KB Output is correct
13 Correct 18 ms 8332 KB Output is correct
14 Correct 23 ms 8284 KB Output is correct
15 Correct 23 ms 8328 KB Output is correct
16 Correct 23 ms 8280 KB Output is correct
17 Correct 7 ms 8280 KB Output is correct
18 Correct 181 ms 17752 KB Output is correct
19 Correct 263 ms 19052 KB Output is correct
20 Correct 129 ms 14004 KB Output is correct
21 Correct 233 ms 19256 KB Output is correct
22 Correct 248 ms 19304 KB Output is correct
23 Correct 268 ms 19616 KB Output is correct
24 Correct 264 ms 19624 KB Output is correct
25 Correct 272 ms 19620 KB Output is correct
26 Correct 249 ms 19628 KB Output is correct
27 Correct 233 ms 19504 KB Output is correct
28 Correct 232 ms 19620 KB Output is correct
29 Correct 236 ms 21068 KB Output is correct
30 Correct 2015 ms 9376 KB Output is correct
31 Execution timed out 3043 ms 7540 KB Time limit exceeded
32 Halted 0 ms 0 KB -