oj.uz

Submission #696951

# Submission time Handle Problem Language Result Execution time Memory
696951 2023-02-07T16:48:48 Z CDuong Izbori (COCI22_izbori) C++17
110 / 110
 611 ms 54288 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42580 KB Output is correct
2 Correct 19 ms 42564 KB Output is correct
3 Correct 19 ms 42580 KB Output is correct
4 Correct 18 ms 42544 KB Output is correct
5 Correct 21 ms 42496 KB Output is correct
6 Correct 18 ms 42536 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42580 KB Output is correct
2 Correct 19 ms 42564 KB Output is correct
3 Correct 19 ms 42580 KB Output is correct
4 Correct 18 ms 42544 KB Output is correct
5 Correct 21 ms 42496 KB Output is correct
6 Correct 18 ms 42536 KB Output is correct
7 Correct 20 ms 42652 KB Output is correct
8 Correct 18 ms 42580 KB Output is correct
9 Correct 20 ms 42608 KB Output is correct
10 Correct 20 ms 42572 KB Output is correct
11 Correct 20 ms 42600 KB Output is correct
12 Correct 21 ms 42644 KB Output is correct
13 Correct 20 ms 42616 KB Output is correct
14 Correct 20 ms 42580 KB Output is correct
15 Correct 20 ms 42580 KB Output is correct
16 Correct 20 ms 42624 KB Output is correct
17 Correct 20 ms 42604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 46844 KB Output is correct
2 Correct 126 ms 47520 KB Output is correct
3 Correct 84 ms 45228 KB Output is correct
4 Correct 130 ms 47532 KB Output is correct
5 Correct 134 ms 47772 KB Output is correct
6 Correct 139 ms 47900 KB Output is correct
7 Correct 153 ms 47828 KB Output is correct
8 Correct 141 ms 47960 KB Output is correct
9 Correct 142 ms 47848 KB Output is correct
10 Correct 140 ms 47912 KB Output is correct
11 Correct 136 ms 48776 KB Output is correct

Subtask #4
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42580 KB Output is correct
2 Correct 19 ms 42564 KB Output is correct
3 Correct 19 ms 42580 KB Output is correct
4 Correct 18 ms 42544 KB Output is correct
5 Correct 21 ms 42496 KB Output is correct
6 Correct 18 ms 42536 KB Output is correct
7 Correct 20 ms 42652 KB Output is correct
8 Correct 18 ms 42580 KB Output is correct
9 Correct 20 ms 42608 KB Output is correct
10 Correct 20 ms 42572 KB Output is correct
11 Correct 20 ms 42600 KB Output is correct
12 Correct 21 ms 42644 KB Output is correct
13 Correct 20 ms 42616 KB Output is correct
14 Correct 20 ms 42580 KB Output is correct
15 Correct 20 ms 42580 KB Output is correct
16 Correct 20 ms 42624 KB Output is correct
17 Correct 20 ms 42604 KB Output is correct
18 Correct 98 ms 46844 KB Output is correct
19 Correct 126 ms 47520 KB Output is correct
20 Correct 84 ms 45228 KB Output is correct
21 Correct 130 ms 47532 KB Output is correct
22 Correct 134 ms 47772 KB Output is correct
23 Correct 139 ms 47900 KB Output is correct
24 Correct 153 ms 47828 KB Output is correct
25 Correct 141 ms 47960 KB Output is correct
26 Correct 142 ms 47848 KB Output is correct
27 Correct 140 ms 47912 KB Output is correct
28 Correct 136 ms 48776 KB Output is correct
29 Correct 152 ms 48776 KB Output is correct
30 Correct 116 ms 45608 KB Output is correct
31 Correct 224 ms 48172 KB Output is correct
32 Correct 611 ms 54288 KB Output is correct
33 Correct 246 ms 48460 KB Output is correct
34 Correct 269 ms 48840 KB Output is correct
35 Correct 198 ms 46836 KB Output is correct
36 Correct 101 ms 45248 KB Output is correct
37 Correct 125 ms 45784 KB Output is correct
38 Correct 167 ms 46424 KB Output is correct
39 Correct 173 ms 46560 KB Output is correct
40 Correct 181 ms 46480 KB Output is correct
41 Correct 171 ms 46620 KB Output is correct
42 Correct 171 ms 46500 KB Output is correct
43 Correct 207 ms 45896 KB Output is correct
44 Correct 212 ms 45952 KB Output is correct
45 Correct 203 ms 45960 KB Output is correct
46 Correct 211 ms 45908 KB Output is correct
47 Correct 211 ms 45960 KB Output is correct
48 Correct 279 ms 45176 KB Output is correct
49 Correct 262 ms 45236 KB Output is correct
50 Correct 257 ms 45644 KB Output is correct
51 Correct 240 ms 45580 KB Output is correct
52 Correct 269 ms 45104 KB Output is correct
53 Correct 261 ms 45124 KB Output is correct
54 Correct 244 ms 45124 KB Output is correct