Submission #1159751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159751		itslq	Specijacija (COCI20_specijacija)	C++20	0 / 110	49 ms	1860 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 (m * (m + 1) / 2 >= 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;

    const int X = n - tri(L - 1) - 1;
    int x = (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));
        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;

    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';
    }
}

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