Submission #1235523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235523		BuiDucManh123	Izbori (COCI22_izbori)	C++20	110 / 110	163 ms	56304 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

int n;
vector<ll> raw;
vector<int> a;
vector<vector<vector<int>>> v;       // v[parity][dish_id] → list of “half‐positions”
vector<vector<map<int,int>>> cnt;    // cnt[parity][dish_id][hei] → count
ll ans = 0;
int bua;

void solve(int id, int k) {
    // “magic” offset so hei never goes negative
    const int ma = 250005;
    auto &vk = v[id][k];
    int res = 0;
    // initial hei = ma − first_halfpos + 1
    int hehe = ma - vk[0] + 1;
    int mi = hehe;

    for (int i = 0; i + 1 < (int)vk.size(); i++) {
        int pos = vk[i];
        // map back to original index q in [1..n]
        int q = (pos - id) * 2 + id;

        // if the element at q equals this dish
        if (a[q] == k) {
            if (hehe <= ma) ans += cnt[id][k][hehe] + 1;
            else          ans += cnt[id][k][hehe];
        }

        // if two consecutive elements are equal, we “step up” hei
        if (a[q] == a[q+1]) {
            if (hehe <= ma) res += cnt[id][k][hehe] + 1;
            else            res += cnt[id][k][hehe];
            hehe++;
        }

        // record current hei
        cnt[id][k][hehe]++;
        ans += res * 2;
        if (q + 1 == n) ans -= res;

        // now “slide” hei back down, one step per gap until the next vk[i+1]
        int gap = vk[i+1] - vk[i] - 1;
        int t = min(hehe - mi, gap);
        bua = hehe - gap;
        while (t--) {
            hehe--;
            if (hehe <= ma) res -= cnt[id][k][hehe] + 1;
            else            res -= cnt[id][k][hehe];
            ans += res * 2;
            // adjust final correction
            if (n % 2 != id && hehe == bua && i == (int)vk.size() - 2)
                ans -= res;
            cnt[id][k][hehe]++;
        }
        // restore hei to bua for next iteration
        hehe = bua;
        mi = min(mi, hehe);
    }

    // handle the very last element if it sits at index n with this parity
    if (n % 2 == id && a[n] == k) {
        if (hehe <= ma) ans += cnt[id][k][hehe] + 1;
        else            ans += cnt[id][k][hehe];
    }
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1) Read
    cin >> n;
    raw.resize(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> raw[i];
    }

    // 2) Compress dish‐values into [0..U-1]
    vector<ll> comp(raw.begin()+1, raw.end());
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int U = comp.size();

    a.assign(n+2, 0);
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(comp.begin(), comp.end(), raw[i]) - comp.begin();
    }

    // 3) Resize our per‐dish data structures
    v    .assign(2, vector<vector<int>>(U));
    cnt  .assign(2, vector<map<int,int>>(U));

    // Build the lists of “half‐positions” for each (parity, dish)
    for (int i = 1; i < n; i++) {
        int id = i % 2;
        int x  = a[i];
        int y  = a[i+1];
        v[id][x].pb(i/2 + id);
        if (x != y) v[id][y].pb(i/2 + id);
    }
    // Append the virtual “end” marker for each dish
    for (int x = 0; x < U; x++) {
        v[1][x].pb(n/2 + 1);
        v[0][x].pb((n+1)/2);
    }

    // 4) Run solve() for every parity & every dish
    for (int id = 0; id < 2; id++) {
        for (int x = 0; x < U; x++) {
            solve(id, x);
        }
    }

    // 5) Output the answer
    cout << ans << "\n";
    return 0;
}

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