Submission #730490

#	Time	Username	Problem	Language	Result	Execution time	Memory
730490		CDuong	Izbori (COCI22_izbori)	C++17	110 / 110	2081 ms	20776 KiB

Main

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const int block = 450;
const ll oo = 1e18;

int dp[mxN], fenw[2 * mxN];
int n, a[mxN], cnt[mxN];
map<int, int> num;
map<int, vi> mp;
bool vis[mxN];
ll ans;

void update(int idx, int val) {
    while(idx < 2 * mxN) {
        fenw[idx] += val;
        idx += (idx & (-idx));
    }
}

int get(int idx) {
    int res = 0;
    while(idx) {
        res += fenw[idx];
        idx -= (idx & (-idx));
    }
    return res;
}

void calc_light() {
    for(int i = 1; i <= n; ++i) {
        int max_len = min(n - i + 1, 2 * block), maxx = 0;
        vi cur;
        for(int len = 1; len <= max_len; ++len) {
            int r = i + len - 1;
            if(!vis[a[r]]) {
                continue;
            }
            cnt[a[r]]++;
            cur.emplace_back(a[r]);
            maxx = max(maxx, cnt[a[r]]);
            if(maxx * 2 > len) {
                ++ans;
            }
        }
        for(int &val : cur) {
            cnt[val] = 0;
        }
    }
}

void calc_heavy(vi &v) {
    memset(fenw, 0, sizeof fenw);
    int cur_sum = mxN, cur_idx = 0;
    update(cur_sum, 1);
    for(int i = 1; i <= n; ++i) {
        if(cur_idx < (int)v.size() && i == v[cur_idx]) {
            ++cur_sum, ++cur_idx;
        }
        else {
            --cur_sum;
        }

        ans += get(cur_sum - 1);
        update(cur_sum, 1);
    }
}

int comp(int val) {
    if(num[val] == 0) {
        num[val] = num.size();
    }
    return num[val];
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = comp(a[i]);
        mp[a[i]].emplace_back(i);
    }
    for(auto &[val, v] : mp) {
        if((int)mp[val].size() < block) {
            vis[val] = true;
        }
        else {
            calc_heavy(v);
        }
    }
    calc_light();
    cout << ans << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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