Submission #1139620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139620		anmattroi	Specijacija (COCI20_specijacija)	C++17	20 / 110	4094 ms	2012 KiB

Main

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;

int n, q, t;
int64_t a[maxn];

int level(int64_t x) {
    int lo = -1, hi = n;
    while (hi-lo>1) {
        int mid = (lo+hi)>>1;
        if (x <= 1LL*(mid+1)*(mid+2)/2) hi = mid;
        else lo = mid;
    }
    return hi;
}

int64_t jump(int64_t x, int &Lv) {
    x -= Lv;
    if (x > a[Lv]) --x;
    --Lv;
    return x;
}


int64_t solve(int64_t x, int64_t y) {
    int Lv1 = level(x), Lv2 = level(y);
    while (Lv1 > Lv2) {x = jump(x, Lv1);}
    while (Lv2 > Lv1) {y = jump(y, Lv2);}
    while (x != y) {
        x = jump(x, Lv1);
        y = jump(y, Lv2);
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q >> t;
    int64_t last = 0;
    int64_t LIM = 1LL * (n+1) * (n+2) / 2;
    for (int i = 1; i <= n; i++) cin >> a[i];

    while (q--) {
        int64_t x, y;
        cin >> x >> y;
        x = (x-1 + t*last) % LIM + 1;
        y = (y-1 + t*last) % LIM + 1;
        cout << (last = solve(x, y)) << "\n";
    }
}
/*
3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3
-------
1
6
2
1
1
*/

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