Submission #1159815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159815		itslq	Specijacija (COCI20_specijacija)	C++20	0 / 110	58 ms	3140 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAX = 2e5 + 5;
const int LOG = 13;
vector<int> A;

int tri(int n) {
    return n * (n + 1) / 2;
}

int getLayer(int n) {
    int l = 1, r = n, m, ans;
    while (l <= r) {
        m = (l + r) >> 1;
        if (tri(m) >= n) {
            ans = m;
            r = --m;
        } else {
            l = ++m;
        }
    }
    return ans;
}

int kpa(int n, int k) {
    if (k == 0) return n;
    const int L = getLayer(n);

    if (L - k < 1) return -1;

    int X = n - tri(L - 1) - 1;
    // cout << X << "&&" << A[L - k] << " " << endl;
    // int x = max(0LL, min(k, X - A[L - k]));
    int x = 0;
    for (int i = L; i >= L - k; i--) if (A[i] <= X) X--, n--;
    // int x = max(L - k, min(L, (int) (upper_bound(A.begin(), A.end(), X) - A.begin()) - 1)) - L + k;

    // int x = min(k, (int) (upper_bound(A.begin() + L - k, A.begin() + L, X) - (A.begin() + L - k)));
    return n - tri(L - 1) + tri(L - k - 1) - x;
}

int LCA(int x, int y) {
    int a = getLayer(x), b = getLayer(y), nx, ny;
    if (a > b) {
        swap(a, b);
        swap(x, y);
    }
    y = kpa(y, b - a);

    if (x == y) return x;

    for (int i = LOG; i >= 0; i--) {
        nx = kpa(x, (1 << i)), ny = kpa(y, (1 << i));
        // cout << i << " " << nx << " " << ny << endl;
        if (nx != ny) x = nx, y = ny;
    }

    return kpa(x, 1);
}

signed main() {
    int N, Q, T, x, y, p = 0;
    cin >> N >> Q >> T;
    const int MOD = tri(N + 1);

    A.resize(N + 2);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        A[i] -= tri(i - 1);
    }
    A[N + 1] = INT_MAX;

    cout << endl << endl;
    for (int t: A) cout << t << " ";
    cout << endl;

    while (Q--) {
        cin >> x >> y;
        if (T) {
            x = (x - 1 + p) % MOD + 1;
            y = (y - 1 + p) % MOD + 1;
        }
        cout << (p = LCA(x, y)) << '\n';
        // cout << kpa(x, y) << endl;
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60