Submission #1252306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252306		EJIC_B_KEDAX	Triple Peaks (IOI25_triples)	C++20	98.80 / 100	1538 ms	100144 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct mst {
    vector<vector<int>> st;
    size_t sz;
    mst(vector<int> a) {
        sz = 1;
        while (sz < a.size()) {
            sz <<= 1;
        }
        st.resize(2 * sz);
        for (int i = 0; i < a.size(); i++) {
            st[sz + i].push_back(a[i]);
        }
        for (int i = sz - 1; i > 0; i--) {
            st[i].resize(st[2 * i].size() + st[2 * i + 1].size());
            ranges::merge(st[2 * i], st[2 * i + 1], st[i].begin());
        }
    }
    int get_same(int l, int r, int v) {
        l += sz; r += sz;
        int res = 0;
        while (l <= r) {
            if (l & 1) {
                res += ranges::upper_bound(st[l], v) - ranges::lower_bound(st[l], v);
                l++;
            }
            if (~r & 1) {
                res += ranges::upper_bound(st[r], v) - ranges::lower_bound(st[r], v);
                r--;
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

ll count_triples(vector<int> h) {
    int n = h.size();
    vector<int> ff = h, ss = h;
    vector<int> prev(n), next(n);
    for (int i = 0; i < n; i++) {
        ff[i] -= i;
        ss[i] += i;
    }
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        if (mp.find(ff[i]) == mp.end()) {
            prev[i] = -1;
        } else {
            prev[i] = mp[ff[i]];
        }
        mp[ff[i]] = i;
    }
    mp.clear();
    for (int i = n - 1; i >= 0; i--) {
        if (mp.find(ss[i]) == mp.end()) {
            next[i] = n;
        } else {
            next[i] = mp[ss[i]];
        }
        mp[ss[i]] = i;
    }
    mst mst1(ff), mst2(ss);

    ll ans = 0;
    auto check1 = [&](int i, int j, int k) -> bool {
        vector<int> x = {abs(i - j), abs(j - k), abs(k - i)}, y = {h[i], h[j], h[k]};
        ranges::sort(x);
        ranges::sort(y);
        return x == y;
    };
    auto check2 = [&](int i, int j, int k) -> bool {
        if (abs(k - i) == h[j] && abs(i - j) == h[k] && abs(j - k) == h[i]) return false;
        return check1(i, j, k);
    };
    auto srt = [](tuple<int, int, int> t) -> tuple<int, int, int> {
        vector<int> x = {get<0>(t), get<1>(t), get<2>(t)};
        ranges::sort(x);
        return {x[0], x[1], x[2]};
    };
    set<tuple<int, int, int>> simp;
    for (int i = 0; i < n; i++) {
        if (i - h[i] >= 0) {
            int j = i - h[i];
            if (j - h[j] >= 0) {
                int l = j - h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
            if (j + h[j] < n) {
                int l = j + h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
            if (i - h[j] >= 0) {
                int l = i - h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
            if (i + h[j] < n) {
                int l = i + h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
        }
        if (i + h[i] < n) {
            int j = i + h[i];
            if (j - h[j] >= 0) {
                int l = j - h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
            if (j + h[j] < n) {
                int l = j + h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
            if (i - h[j] >= 0) {
                int l = i - h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
            if (i + h[j] < n) {
                int l = i + h[j];
                if (check2(i, j, l)) {
                    simp.insert(srt({i, j, l}));
                }
            }
        }
    }
    ans += simp.size();
    simp.clear();
    for (int i = 0; i < n; i++) {
        if (mst1.get_same(0, i, ff[i]) < mst2.get_same(i, n - 1, ss[i])) {
            int cur = prev[i];
            while (cur != -1) {
                if (i + h[cur] < n && check1(cur, i, i + h[cur])) {
                    ans++;
                }
                cur = prev[cur];
            }
        } else {
            int cur = next[i];
            while (cur != n) {
                if (i - h[cur] >= 0 && check1(i - h[cur], i, cur)) {
                    ans++;
                }
                cur = next[cur];
            }
        }
    }

    return ans;
}

mt19937 mt(123);

vector<int> construct_range(int n, int _K) {
    int D, CD;
    if (n == 200000) {
        D = 418;
        CD = 210;
    }
    if (n == 100000) {
        D = 252;
        CD = 126;
    }
    if (n == 30000) {
        D = 160;
        CD = 80;
    }
    if (n == 5000) {
        D = 60;
        CD = 32;
    }
    if (n == 500) {
        D = 20;
        CD = 10;
    }
    if (n == 20) {
        vector<int> ans = {3, 3, 1, 2, 1, 4, 5, 2, 3, 3, 1, 2, 1, 4, 3, 2, 3, 1, 1, 2};
        return ans;
    }
    n--;
    vector<int> ans(n, 0);
    for (int i = 0; i < CD; i++) {
        for (int j = 0; j < D; j++) {
            ans[i * D + j] = (n + 1) / 2 - D - i * D + j;
        }
    }
    for (int i = 0; i < CD; i++) {
        for (int j = 0; j < D; j++) {
            ans[n - 1 - (i * (D + 2) + j)] = (n + 1) / 2 - D - i * D + j - 2 * i;
        }
    }

    int cnt = 0;

    vector<int> ch(n, -1);

    for (int i = 0; i < CD; i++) {
        for (int j = 0; j < CD; j++) {
            int hui = (n - 1 + i * D - j * (D + 2)) / 2 - (ans[i * D] - ans[n - 1 - (j * (D + 2))]) / 2;
            // if (hui >= CD * D && hui < n - CD * (D + 2)) {
                cnt++;
                ch[hui] = ans[i * D] + hui - i * D;
            // }
        }
    }
    for (int i = 0; i < n; i++) {
        if (ch[i] != -1) {
            ans[i] = ch[i];
        }
    }

    for (int i = 0; i < n; i++) {
        if (ans[i] == 0) {
            ans[i] = mt() % 2 + 1;
        }
        ans[i] = max(min(ans[i], n - 1), 1);
    }
    if (n == 499) {
        int kk = count_triples(ans);
        for (int _ = 0; _ < 3000; _++) {
            vector<int> old_ans = ans;
            ans[mt() % n] = mt() % 10 + 1;
            int nw = count_triples(ans);
            if (nw > kk) {
                kk = nw;
            } else {
                ans = old_ans;
            }
        }
    }
    return ans;
}

• 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: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 4.4275 / 5
• Subtask 9: 4.6671 / 5
• Subtask 10: 4.8577 / 5
• Subtask 11: 5 / 5
• Subtask 12: 4.8468 / 5