#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
//#define int long long
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 400 * 1000 + 10;
int n, q, t;
ll seq[nax];
struct Node {
ll g;
int ti, lft, rght;
};
vector<Node>T1[(1<<19)];
vector<Node>T2[nax];
vector<Node>T3[(1<<19)];
int R;
vi V[nax];
map<ll,int>sc;
ll starting[nax];
void add(int a, int b, int x, int ti, int l, int r, int v) {
if(a <= l && r <= b) {
if(v >= R) {
T1[v].PB({T1[v].back().g + x, ti, -1, -1});
} else {
T1[v].PB({T1[v].back().g + x, ti, (int)T1[2*v].size() - 1, (int)T1[2*v+1].size() - 1});
}
return;
}
int mid = (l + r) / 2;
if(a <= mid) add(a, b, x, ti, l, mid, v*2);
if(b > mid) add(a,b,x,ti,mid + 1,r,v*2+1);
T3[v].PB({max(T3[2*v].back().g + T1[2*v].back().g, T3[2*v+1].back().g + T1[2*v+1].back().g), ti, (int)T3[2*v].size() - 1, (int)T3[2*v+1].size() - 1});
T1[v].PB({T1[v].back().g, ti, (int)T1[2*v].size() - 1, (int)T1[2*v+1].size() - 1});
}
inline void ustaw(int a, ll x, int ti) {
T2[a].PB({x, ti, -1,-1});
}
inline ll askVal(int x) {
return T2[x].back().g;
}
inline int g(vector<Node>&vec, int ti) {
int low = 0, high = (int)vec.size() - 1, mid;
while(low <= high) {
mid = (low + high) >> 1;
if(vec[mid].ti >= ti) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low - 1;
}
inline ll askVal2(int x, int ti) {
int ind = g(T2[x], ti);
return T2[x][ind].g;
}
inline int f(int x) {
int v = 1;
int delta = 0;
while(v < R) {
delta += T1[v].back().g;
if(T3[2*v].back().g + T1[2*v].back().g + delta >= x) {
v = v * 2;
} else {
v = v * 2 + 1;
}
}
v -= R;
if(v > n + 1) v = n + 2;
return v;
}
inline int f2(int x, int ti) {
int v = 1;
int ind = g(T1[v], ti);
int ind2 = g(T3[v], ti);
int delta = 0;
while(v < R) {
delta += T1[v][ind].g;
if(T3[2*v][T3[v][ind2].lft].g + T1[2*v][T1[v][ind].lft].g + delta >= x) {
ind = T1[v][ind].lft;
ind2 = T3[v][ind2].lft;
v = v * 2;
} else {
ind = T1[v][ind].rght;
ind2 = T3[v][ind2].rght;
v = v * 2 + 1;
}
}
v -= R;
if(v > n + 1) v = n + 2;
return v;
}
inline ll ustal(ll x) {
int low = 1, high = n + 1, mid;
while(low <= high) {
mid = (low + high) >> 1;
if(starting[mid] <= x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
low--;
int k = x - starting[low] + 1;
int dep = low;
int pos = f2(k, dep);
return askVal2(pos, dep);
}
int par[nax][19], dp[nax];
ll inv[nax];
inline void dfs(int x) {
for(int nbh : V[x]) {
dp[nbh] = dp[x] + 1;
dfs(nbh);
par[nbh][0] = x;
}
}
inline int lca(int a, int b) {
if(dp[a] < dp[b]) swap(a, b);
for(int i = 18; i >= 0; --i) {
if(dp[par[a][i]] >= dp[b]) {
a = par[a][i];
}
}
if(a == b) return -a;
for(int i = 18; i >= 0; --i) {
if(par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
__int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> t;
ll start = 1;
for(int i = 1; i <= n; ++i) {
starting[i] = start;
cin >> seq[i];
sc[seq[i]];
start += i;
}
starting[n + 1] = start;
R = 1;
while(R <= n + 2) R *= 2;
for(int i = 1; i < 2 * R; ++i) {
T1[i].PB({0, n + 2});
T3[i].PB({0, n + 2});
}
//cerr << "Done0\n";
for(int i = 1; i <= n + 1; ++i) {
add(i, i, i, n + 1, 0, R - 1, 1);
ustaw(i, start + i - 1, n + 1);
sc[start + i - 1];
}
//cerr << "Done\n";
int nr = 1;
for(auto &it : sc) {
inv[nr] = it.ST;
it.ND = nr++;
}
for(int i = n; i >= 1; --i) {
// val = a[i] + i - start + 1
int val = seq[i] + i - start + 1;
int pos = f(val + 1);
int l = f(val);
//cout << pos << " " << l << " " << r << "\n";
ll val1 = askVal(l);
ll val2 = askVal(pos);
V[sc[seq[i]]].PB(sc[val1]);
V[sc[seq[i]]].PB(sc[val2]);
ustaw(l, seq[i], i);
add(pos, n + 1, -1, i, 0, R - 1, 1);
start -= i;
}
assert(n <= 100000);
ll ans = 0;
dp[1] = 1;
dfs(sc[1]);
for(int s = 1; s <= 18; ++s) {
for(int i = 1; i <= nr; ++i) {
par[i][s] = par[par[i][s - 1]][s - 1];
}
}
while(q--) {
ll x, y;
cin >> x >> y;
x = ((x - 1 + t * ans)%((ll)(n+1)*(n+2)/2)) + 1;
y = ((y - 1 + t * ans)%((ll)(n+1)*(n+2)/2)) + 1;
ll xa = ustal(x);
ll ya = ustal(y);
if(xa == ya) {
cout << min(x, y) << "\n";
ans = min(x, y);
continue;
}
int l = lca(sc[xa], sc[ya]);
if(l < 0) {
cout << min(x, y) << "\n";
ans = min(x, y);
continue;
}
cout << inv[l] << "\n";
ans = inv[l];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3150 ms |
1048576 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3150 ms |
1048576 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3150 ms |
1048576 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3239 ms |
1048576 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
