제출 #696723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696723		CDuong	Izbori (COCI22_izbori)	C++17	0 / 110	99 ms	9552 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;
} segtree[8 * mxN];

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

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

ll calc(ll l, ll r) {
    ll len = r - l + 1;
    return ((l + r) * len / 2);
}

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

    ll tmp = segtree[idx].lazy, mid = (l + r) >> 1;

    segtree[idx << 1].val += (mid - l + 1) * tmp;
    segtree[idx << 1].val1 += calc(1, mid - l + 1) * tmp;
    segtree[idx << 1].lazy += tmp;
    
    segtree[idx << 1 | 1].val += (r - mid) * tmp;
    segtree[idx << 1 | 1].val1 += calc(1, r - mid) * tmp;
    segtree[idx << 1 | 1].lazy += tmp;

    segtree[idx].lazy = 0;
}

void merge(node &res, node &a, node &b, ll len) {
    res.val = a.val + b.val;
    res.val1 = a.val1 * len + b.val1;
}

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) {
        segtree[idx].val += (ll)(val) * (ll)(r - l + 1);
        segtree[idx].val1 += (ll)(val) * calc(1, r - l + 1);
        segtree[idx].lazy += val;
        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);

    merge(segtree[idx], segtree[idx << 1], segtree[idx << 1 | 1], r - mid);
}

ll get_normal(int l, int r, int idx, int u, int v) {
    if(v < l || r < u)
        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(int l, int r, int idx, int u, int v) {
    // cout << l << " " << r << " " << idx << " " << u << " " << v << endl;
    if(v < l || r < u)
        return {0, 0};
    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(mid + 1, r, idx << 1 | 1, u, v);
    if(v < mid + 1) return get(l, mid, idx << 1, u, v);
    else {
        pll tmp = get(l, mid, idx << 1, u, v);
        pll tmp1 = get(mid + 1, r, idx << 1 | 1, u, v);
        ll len = v - mid;
        ll sum = tmp1.ff + tmp.ff + tmp.ss * len;
        ll sum1 = tmp.ss + tmp1.ss;
        return {sum, sum1};
    }
}

ll get_sum(int l, int r) {
    // cout << "boom: " << l << " " << r << endl;
    if(l == r)
        return get_normal(1, 2 * n + 1, 1, 1, l - 1);
    pll res = get(1, 2 * n + 1, 1, l, r - 1);
    // cout << endl << "l = " << l << ", r - 1 = " << r - 1 << ", res = " << res.ff << endl;
    if(l == 1)
        return res.ff;
    res.ff += get_normal(1, 2 * n + 1, 1, 1, l - 1) * (ll)(r - l + 1);
    return res.ff;
}

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 val : num)
        mp[val] = ++cnt;
    for(int i = 1; i <= n; ++i) {
        a[i] = mp[a[i]];
        appearance[a[i]].pb(i);
    }

    for(int i = 1; i <= (int)num.size(); ++i) {
        vector<op> ops;
        int sz = appearance[i].size();
        appearance[i].pb(n + 1);
        update(1, 2 * n + 1, 1, n - appearance[i][0] + 2, n + 1, 1);
        ops.pb({n - appearance[i][0] + 2, n + 1, -1});
        // cout << 0 << " " << n - appearance[i][0] - n + 1 << endl;
        int cur_sum = n - appearance[i][0] + 3;

        for(int j = 0; j < sz; ++j) {
            int cur = appearance[i][j], nxt = appearance[i][j + 1];
            int len = nxt - cur, nxt_sum = cur_sum - len + 1;

            // cout << cur << ": ";
            // cout << cur_sum - n - 1 << " " << nxt_sum - n - 1 << " = ";
            ll tmp = get_sum(nxt_sum, cur_sum);
            // cout << tmp << endl;
            ans += tmp;
            update(1, 2 * n + 1, 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 + 1, 1, st, en, val);
        // cout << endl;
    }

    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: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 70