Submission #696951

#	Time	Username	Problem	Language	Result	Execution time	Memory
696951		CDuong	Izbori (COCI22_izbori)	C++17	110 / 110	611 ms	54288 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 pll pair<ll, ll>
#define vi vector<int>
using namespace std;

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

struct node {
    ll val, val1, lazy;
    node() {val = val1 = lazy = 0;}
} segtree[8 * mxN];

struct op {int st, en, val;};

ll ans;
int n, a[mxN], cnt;
map<int, int> mp;
vi num, appearance[mxN];

void update_node(int idx, int val, int l, int r) {
    ll tmp = (ll)(r - l + 2) * (ll)(r - l + 1) / 2;
    segtree[idx].val += (r - l + 1) * (ll)val;
    segtree[idx].val1 += tmp * val;
    segtree[idx].lazy += val;
}

void down(int idx, int l, int r) {
    if(segtree[idx].lazy == 0)
        return;

    int val = segtree[idx].lazy, mid = (l + r) >> 1;
    update_node(idx << 1, val, l, mid);
    update_node(idx << 1 | 1, val, mid + 1, r);
    segtree[idx].lazy = 0;

}

void update(int l, int r, int idx, int u, int v, int val) {
    if(v < l || r < u)
        return;
    if(u <= l && r <= v) {
        update_node(idx, val, l, r);
        return;
    }

    down(idx, l, r);

    int mid = (l + r) >> 1;
    update(l, mid, idx << 1, u, v, val);
    update(mid + 1, r, idx << 1 | 1, u, v, val);

    segtree[idx].val = segtree[idx << 1].val + segtree[idx << 1 | 1].val;
    segtree[idx].val1 = segtree[idx << 1].val1 + segtree[idx << 1 | 1].val1 + segtree[idx << 1].val * (r - mid);
}

ll get_normal(int l, int r, int idx, int u, int v) {
    if(r < u || v < l)
        return 0;
    if(u <= l && r <= v)
        return segtree[idx].val;

    down(idx, l, r);

    int mid = (l + r) >> 1;
    return (get_normal(l, mid, idx << 1, u, v) + get_normal(mid + 1, r, idx << 1 | 1, u, v));
}

pll get_sum(int l, int r, int idx, int u, int v) {
    if(u <= l && r <= v)
        return {segtree[idx].val1, segtree[idx].val};

    down(idx, l, r);

    int mid = (l + r) >> 1;
    if(mid < u) return get_sum(mid + 1, r, idx << 1 | 1, u, v);
    if(v < mid + 1) return get_sum(l, mid, idx << 1, u, v);

    pll tmp = get_sum(l, mid, idx << 1, u, v);
    pll tmp1 = get_sum(mid + 1, r, idx << 1 | 1, u, v);

    pll res;
    res.ff = tmp1.ff + tmp.ff + tmp.ss * (min(r, v) - mid);
    res.ss = tmp.ss + tmp1.ss;

    return res;
}

ll get(int l, int r) {
    if(l == r)
        return get_normal(1, 2 * n + 2, 1, 1, l - 1);

    ll sum = get_normal(1, 2 * n + 2, 1, 1, l - 1) * (r - l + 1);
    sum += get_sum(1, 2 * n + 2, 1, l, r - 1).ff;

    return sum;
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        num.pb(a[i]);
    }
    
    sort(all(num));
    num.erase(unique(all(num)), num.end());

    for(int i : num) {
        mp[i] = ++cnt;
        appearance[cnt].pb(0);
    }

    for(int i = 1; i <= n; ++i)
        appearance[mp[a[i]]].pb(i);

    for(int i = 1; i <= cnt; ++i) {
        int sz = appearance[i].size();
        appearance[i].pb(n + 1);
        int cur_sum = n + 2;

        vector<op> ops;

        for(int j = 0; j < sz; ++j) {
            int nxt_sum = cur_sum - (appearance[i][j + 1] - appearance[i][j]) + 1;
            int tmp = get(nxt_sum, cur_sum);
            ans += tmp;
            update(1, 2 * n + 2, 1, nxt_sum, cur_sum, 1);
            ops.pb({nxt_sum, cur_sum, -1});
            cur_sum = nxt_sum + 1;
        }

        for(auto [st, en, val] : ops)
            update(1, 2 * n + 2, 1, st, en, val);
    }

    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