Submission #1262814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262814		Canuc80k	Triple Peaks (IOI25_triples)	C++20	51 / 100	2095 ms	47904 KiB

triples

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

ll res = 0;

void add(ll i, ll j, ll k) {
    res ++;
}

static inline ll pack_comp(int x, int y, int m) {
    return (ll)x * (ll)m + (ll)y;
}

long long countr(const vector<int> &a_orig, const vector<int> &b_orig) {
    int n = (int)a_orig.size();
    if (n == 0) return 0;
    int T = max(1, (int)std::sqrt((double)n));

    vector<int> vals;
    vals.reserve(2 * n);
    for (int v : a_orig) vals.push_back(v);
    for (int v : b_orig) vals.push_back(v);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = (int)vals.size();

    unordered_map<int,int> val2id;
    val2id.reserve(m * 2);
    for (int i = 0; i < m; ++i) val2id[vals[i]] = i;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        a[i] = val2id.at(a_orig[i]);
        b[i] = val2id.at(b_orig[i]);
    }

    vector<vector<int>> posA(m);
    for (int i = 0; i < n; ++i) posA[a[i]].push_back(i);

    vector<ll> keys(n);
    for (int i = 0; i < n; ++i) keys[i] = pack_comp(a[i], b[i], m);

    vector<ll> uniq_keys = keys;
    sort(uniq_keys.begin(), uniq_keys.end());
    uniq_keys.erase(unique(uniq_keys.begin(), uniq_keys.end()), uniq_keys.end());
    int K = (int)uniq_keys.size();

    vector<vector<int>> posPairById(K);
    for (int i = 0; i < n; ++i) {
        int id = int(lower_bound(uniq_keys.begin(), uniq_keys.end(), keys[i]) - uniq_keys.begin());
        posPairById[id].push_back(i);
    }

    auto find_key_id = [&](ll key)->int {
        auto it = lower_bound(uniq_keys.begin(), uniq_keys.end(), key);
        if (it == uniq_keys.end() || *it != key) return -1;
        return int(it - uniq_keys.begin());
    };

    vector<int> heavyY;
    vector<char> isHeavy(m, 0);
    for (int v = 0; v < m; ++v) {
        if (!posA[v].empty() && (int)posA[v].size() > T) {
            heavyY.push_back(v);
            isHeavy[v] = 1;
        }
    }

    ll ans = 0;

    for (int k = 0; k < n; ++k) {
        int x = a[k], y = b[k];
        if (isHeavy[y]) continue;
        const auto &Iy = posA[y];
        for (int t = 0; t < (int)Iy.size() && Iy[t] < k; ++t) {
            int i = Iy[t];
            ll key = pack_comp(x, b[i], m);
            int id = find_key_id(key);
            if (id == -1) continue;
            const auto &vec = posPairById[id];
            int L = int(upper_bound(vec.begin(), vec.end(), i) - vec.begin());
            int R = int(lower_bound(vec.begin(), vec.end(), k) - vec.begin());
            ans += (ll)(R - L);
        }
    }

    for (int y : heavyY) {
        vector<int> cntI(m, 0);
        vector<ll> P(m, 0);
        for (int t = 0; t < n; ++t) {
            if (b[t] == y) {
                ans += P[a[t]];
            }
            P[a[t]] += (ll)cntI[b[t]];
            if (a[t] == y) cntI[b[t]]++;
        }
    }

    return ans;
}

long long count_triples(std::vector<int> H) {
    res = 0;
    for (int k = 2; k < (int)H.size(); k ++) {
        int i = k - H[k];
        if (i < 0 || H[i] >= H[k]) continue;
        int j1 = k - H[i], j2 = i + H[i];
        if (j1 < 0 || H[j1] >= H[k] || H[j1] != j1 - i) j1 = -1;
        if (j2 >= k || H[j2] >= H[k] || H[j2] != k - j2) j2 = -1;
        if (j1 != -1) add(i, j1, k);
        if (j2 != -1 && j1 != j2) add(i, j2, k);
    }

    for (int i = 0; i + 2 < (int)H.size(); i ++) {
        int k = i + H[i];
        if (k >= (int)H.size() || H[k] >= H[i]) continue;
        int j1 = k - H[k], j2 = i + H[k];
        if (j1 < 0 || H[j1] >= H[i] || H[j1] != j1 - i) j1 = -1;
        if (j2 >= k || H[j2] >= H[i] || H[j2] != k - j2) j2 = -1;
        if (j1 != -1) add(i, j1, k);
        if (j2 != -1 && j1 != j2) add(i, j2, k);
    }

    for (int i = 0; i + 2 < (int)H.size(); i ++) {
        int j = i + H[i];
        if (j >= (int)H.size() || H[j] <= H[i]) continue;
        int k = i + H[j];
        if (k >= (int)H.size() || H[k] >= H[j] || k - H[k] != j || k - j == H[i]) k = -1;
        if (k != -1) add(i, j, k);
    }

    vector<int> a, b;
    a.reserve(H.size());
    b.reserve(H.size());
    for (int i = 0; i < (int)H.size(); i ++) a.push_back(H[i] + i);
    for (int i = 0; i < (int)H.size(); i ++) b.push_back(i - H[i]);

    res += countr(a, b);
    return res;
}

int rnd_int(int l, int r) {
    if (l > r) swap(l, r);
    static thread_local mt19937 gen((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> dist(l, r);
    return dist(gen);
}

std::vector<int> construct_range(int M, int K) {
    if (M <= 0) return {};
    vector<int> save;
    ll attempt = max(1, (int)(10000000 / M));
    long long best = -1;
    while (attempt--) {
        vector<int> resv;
        resv.reserve(M);
        int rmax = max(1, (int)std::sqrt(M));
        for (int i = 0; i < M; i ++) resv.push_back(rnd_int(1, rmax));
        ll x = count_triples(resv);
        if (x > best) { best = x; save = resv; }
    }
    return save;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 0 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5