#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1ll << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountint
#define file "test"
template<class X, class Y>
bool minz(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} return false;
}
template<class X, class Y>
bool maxz(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} return false;
}
const int N = 1e6 + 5;
const int oo = (int) 1e16;
const int mod = 1e9 + 7; // 998244353;
struct node {
int val = 0, comp = 0;
node *l, *r;
node (int u, int v) : val(u), comp(v), l(nullptr), r(nullptr){}
node (node *u, node *v){
l = u;
r = v;
val = l -> val + r -> val;
}
node (node *cp) : val(cp -> val), l(cp -> l), r(cp -> r){}
};
node *build (int l, int r){
if (l == r) return new node(1, l);
int mid = (l + r) >> 1;
return new node(build(l, mid), build(mid + 1, r));
}
node *update (node *i, int l, int r, int u, int val, int comp){
if (l == r) return new node(val, comp);
int mid = (l + r) >> 1;
if (u <= mid)
return new node (update(i -> l, l, mid, u, val, comp), i -> r);
return new node (i -> l, update(i -> r, mid + 1, r, u, val, comp));
}
pii walk (node *i, int l, int r, int u){
if (l == r) return mp(l, i -> comp);
int mid = (l + r) >> 1;
if (u <= (i -> l) -> val){
return walk(i -> l, l, mid, u);
}
return walk(i -> r, mid + 1, r, u - (i -> l) -> val);
}
int get (node *i, int l, int r, int u, int v){
if (l > v || r < u || u > v) return 0;
if (l >= u && r <= v) return i -> val;
int mid = (l + r) >> 1;
return get(i -> l, l, mid, u, v) + get(i -> r, mid + 1, r, u, v);
}
ll a[N], f[N], t, u, v;
int n, q, cc, d[N], up[20][N];
vector <int> g[N];
node *root[N];
int getdep(ll x){
forr (i, 1, n){
if (x - i <= 0)
return i;
x -= i;
}
return n + 1;
}
void dfs (int u){
for (int v : g[u]){
d[v] = d[u] + 1;
up[0][v] = u;
//cout << u << " " << v << "\n";
forr (i, 1, 18){
up[i][v] = up[i - 1][up[i - 1][v]];
}
dfs(v);
}
}
int jump (int u, int v){
forr (i, 0, 18)
if (bit(v, i))
u = up[i][u];
return u;
}
int lca (int u, int v){
if (d[u] < d[v]) swap(u, v);
u = jump(u, d[u] - d[v]);
//cout << u << " " << v << endl;
if (u == v) return u;
ford (i, 18, 0)
if (up[i][u] != up[i][v]){
u = up[i][u];
v = up[i][v];
}
return up[0][u];
}
int getcc (int x){
int u = getdep(x);
int v = x - (u * (u - 1) / 2);
//cout << x << " " << u << " " << v << "\n";
return walk(root[u], 1, n + 1, v).nd;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef hqm
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
cin >> n >> q >> t;
forr (i, 1, n){
cin >> a[i];
}
forr (i, 1, n + 1)
f[i] = n * (n + 1) / 2 + i;
root[n + 1] = build(1, n + 1);
cc = n + 1;
ford (i, n, 1){
root[i] = root[i + 1];
int w = a[i] - i * (i - 1) / 2;
//cout << w << "\n";
pii u = walk(root[i], 1, n + 1, w);
pii v = walk(root[i], 1, n + 1, w + 1);
//cout << u.st << " " << u.nd << " " << v.st << " " << v.nd << "\n";
root[i] = update(root[i], 1, n + 1, u.st, 1, ++cc);
root[i] = update(root[i], 1, n + 1, v.st, 0, 0);
g[cc].pb(u.nd);
g[cc].pb(v.nd);
f[cc] = a[i];
}
dfs(cc);
ll pre = 0;
while (q--){
cin >> u >> v;
u = (u - 1 + pre * t) % ((n + 1) * (n + 2) / 2) + 1;
v = (v - 1 + pre * t) % ((n + 1) * (n + 2) / 2) + 1;
int uu = getcc(u);
int vv = getcc(v);
// cout << u << " " << uu << endl;
// cout << v << " " << vv << endl;
if (uu == vv){
pre = min(u, v);
cout << min(u, v) << endl;
continue;
}
int s = lca(uu, vv);
// cout << s << endl;
if (s == uu){
pre = u;
cout << u << endl;
} else
if (s == vv){
pre = v;
cout << v << endl;
} else {
pre = f[s];
cout << f[s] << endl;
}
}
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
300208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
300208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
300208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4058 ms |
302560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
