// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
struct Node {
Node *l, *r;
int lo,hi,val;
Node(int L,int R) : lo(L),hi(R) {
val=hi-lo;
if(hi-lo!=1) {
int mid=(lo+hi)/2;
l=new Node(lo,mid);
r=new Node(mid,hi);
}
}
Node() {;}
int query(int L,int R) {
if(hi<=L||R<=lo)return 0;
if(L<=lo&&hi<=R)return val;
return l->query(L,R)+r->query(L,R);
}
int walk(int indx) {
//cout<<"lo = "<<lo<<" hi = "<<hi<<" indx = "<<indx<<endl;
if(hi-lo==1)return lo;
if(indx<=l->val)return l->walk(indx);
else return r->walk(indx - l->val);
}
};
Node *roots[200001];
int n,q,pos;
void new_root(int change) {
roots[pos-1]=new Node();
Node *cur=roots[pos-1],*prev=roots[pos];
while(1) {
cur->val=prev->val-1;
cur->lo=prev->lo;
cur->hi=prev->hi;
if(cur->hi - cur->lo==1) break;
int mid=(cur->lo+cur->hi)/2;
if(change < mid) {
cur->r=prev->r;
cur->l=new Node();
cur=cur->l;
prev=prev->l;
} else {
cur->l=prev->l;
cur->r= new Node();
cur=cur->r;
prev=prev->r;
}
}
--pos;
}
int cnt;
vii components[200001];
ll triangles[200001],vals[400001],depth[400001];
ll params[200001];
int jmp[20][400001];
ll lca(int u,int v) {
if(depth[u]<depth[v])swap(u,v);
per(j,0,20)if(depth[u]-depth[v]>=(1<<j))u=jmp[j][u];
if(u==v)return vals[u];
per(j,0,20)if(jmp[j][u]!=jmp[j][v]) {
u=jmp[j][u];
v=jmp[j][v];
}
u=jmp[0][u];
return vals[u];
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
ll t;
cin>>n>>q>>t;
cnt=n*2+1;
pos=n;
roots[n]=new Node(0,n+1);
triangles[0]=0;
rep(i,0,n+1) {
triangles[i+1]=ll(i+1)*ll(i+2)/2LL;
components[i].emplace_back(n, --cnt);
vals[cnt]=ll(n)*ll(n+1)/2LL+i+1;
}
rep(i,0,n)cin>>params[i];
per(i,0,n) {
int before=roots[pos]->walk(params[i]-triangles[i]);
int change=roots[pos]->walk(params[i]-triangles[i]+1);
int component=components[before].back().second;
jmp[0][component]=--cnt;
component=components[change].back().second;
jmp[0][component]=cnt;
vals[cnt]=params[i];
components[before].emplace_back(i,cnt);
new_root(change);
//cout<<"i = "<<i<<" indx = "<<params[i] - triangles[i]+1<<" change = "<<change+1<<endl;
}
//pos=1;
//rep(i,1,n+2)rep(j,0,i)cout<<"val = "<<pos++<<" indx = "<<roots[i-1]->walk(j+1)+1<<endl;
jmp[0][0]=0;
per(j,1,20)rep(i,0,n*2+1) jmp[j][i]=jmp[j-1][jmp[j-1][i]];
rep(i,0,n+1)reverse(all(components[i]));
rep(i,0,n*2+1) {
int d=0,u=i;
per(j,0,20)if(jmp[j][u]) {
d+=1<<j;
u=jmp[j][u];
}
d+=(u!=0);
depth[i]=d;
}
ll prev=0;
while(q--) {
ll a,b;
cin>>a>>b;
a=((a-1+t*prev)%triangles[n+1])+1;
b=((b-1+t*prev)%triangles[n+1])+1;
int layer1=lower_bound(triangles,triangles+n+2,a)-triangles-1;
int layer2=lower_bound(triangles,triangles+n+2,b)-triangles-1;
int pos1=roots[layer1]->walk(a-triangles[layer1]);
int pos2=roots[layer2]->walk(b-triangles[layer2]);
int u=lower_bound(all(components[pos1]), ii(layer1,0))->second;
int v=lower_bound(all(components[pos2]), ii(layer2,0))->second;
prev=min(lca(u,v),min(a,b));
cout<<prev<<'\n';
//cout<<"val = "<<a+1<<" layer = "<<layer1+1<<" indx = "<<pos1+1<<" u = "<<u+1<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
577 ms |
252424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
577 ms |
252424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
577 ms |
252424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1721 ms |
258748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
