#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5;
int N, Q, T;
ll A[MAXN+10];
struct BIT
{
int tree[MAXN+10];
void update(int i, int k)
{
for(; i<=N+1; i+=(i&-i))
{
tree[i]+=k;
}
}
int query(int i)
{
int ret=0;
for(; i>0; i-=(i&-i))
{
ret+=tree[i];
}
return ret;
}
}bit;
int B[MAXN+10];
int par[MAXN+10], spa[MAXN+10][30], dep[MAXN+10];
int L[MAXN+10], R[MAXN+10];
struct SEG
{
vector<pii> tree[MAXN*4+10];
void update(int node, int tl, int tr, int l, int r, pii k)
{
if(l<=tl && tr<=r)
{
tree[node].push_back(k);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
}
void init(int node, int tl, int tr)
{
sort(tree[node].begin(), tree[node].end());
if(tl==tr) return;
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
}
int query(int node, int tl, int tr, int p, int k)
{
int val=lower_bound(tree[node].begin(), tree[node].end(), pii(k, 987654321))-tree[node].begin();
if(tl==tr) return val;
int mid=tl+tr>>1;
if(p<=mid) return query(node*2, tl, mid, p, k)+val;
else return query(node*2+1, mid+1, tr, p, k)+val;
}
int query2(int node, int tl, int tr, int p, int k)
{
auto it=lower_bound(tree[node].begin(), tree[node].end(), pii(k, 987654321));
if(it!=tree[node].begin())
{
it--;
if(it->first==k) return it->second;
}
if(tl==tr) assert(0);
int mid=tl+tr>>1;
if(p<=mid) return query2(node*2, tl, mid, p, k);
else return query2(node*2+1, mid+1, tr, p, k);
}
}seg;
int level(ll x)
{
int lo=1, hi=N+2;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if((ll)mid*(mid-1)/2<x) lo=mid;
else hi=mid;
}
return lo;
}
int lca(int u, int v)
{
if(dep[u]>dep[v]) swap(u, v);
for(int i=20; i>=0; i--) if(dep[spa[v][i]]>=dep[u]) v=spa[v][i];
if(u==v) return u;
for(int i=20; i>=0; i--) if(spa[u][i]!=spa[v][i]) u=spa[u][i], v=spa[v][i];
return spa[u][0];
}
int getv(ll x)
{
if(x==1) return N+1;
int l=level(x);
int p=x-(ll)l*(l-1)/2;
int lo=0, hi=N+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
//printf("?? %d %d -> %d\n", l, mid, seg.query(1, 1, N+1, l, mid));
if(seg.query(1, 1, N+1, l, mid)>=p) hi=mid;
else lo=mid;
}
//printf("!! %d %d\n", l, hi);
int val=seg.query2(1, 1, N+1, l, hi);
//printf("GETV %lld %d\n", x, val);
return val;
}
int main()
{
scanf("%d%d%d", &N, &Q, &T);
for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
for(int i=1; i<=N+1; i++) bit.update(i, 1);
for(int i=1; i<=N+1; i++)
{
B[i]=i, L[i]=R[i]=i;
dep[i]=N+1;
}
for(int i=N; i>=1; i--)
{
int p=A[i]-(ll)i*(i-1)/2;
int l, r;
int lo=0, hi=N+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(bit.query(mid)<p) lo=mid;
else hi=mid;
}
l=hi;
lo=0, hi=N+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(bit.query(mid)<p+1) lo=mid;
else hi=mid;
}
r=hi;
par[B[l]]=i+N+1;
par[B[r]]=i+N+1;
spa[B[l]][0]=i+N+1;
spa[B[r]][0]=i+N+1;
dep[i+N+1]=i;
L[i+N+1]=L[B[l]];
R[i+N+1]=R[B[r]];
bit.update(r, -1);
B[r]=0; B[l]=i+N+1;
}
//for(int i=1; i<=N+N+1; i++) printf("%d : %d\n", i, L[i]);
for(int i=1; i<=N+1; i++)
{
int l=par[i]-N, r=N+1;
//printf("%d : %d %d\n", i, l, r);
seg.update(1, 1, N+1, l, r, pii(L[i], i));
}
for(int i=N+3; i<=N+N+1; i++)
{
int l=par[i]-N, r=i-N-1;
//printf("%d : %d %d\n", i, l, r);
seg.update(1, 1, N+1, l, r, pii(L[i], i));
}
seg.update(1, 1, N+1, 1, 1, pii(1, N+2));
spa[N+2][0]=N+2;
for(int i=1; i<=20; i++) for(int j=1; j<=N+N+1; j++) spa[j][i]=spa[spa[j][i-1]][i-1];
seg.init(1, 1, N+1);
//for(int i=1; i<=N+1; i++) if(seg.query(1, 1, N+1, i, 987654321)!=i) while(1);
ll bef=0;
while(Q--)
{
ll u, v;
scanf("%lld%lld", &u, &v);
u=(((u-1+T*bef)%((ll)(N+1)*(N+2)/2)))+1;
v=(((v-1+T*bef)%((ll)(N+1)*(N+2)/2)))+1;
//printf("%lld %lld\n", u, v);
int lu, lv;
lu=getv(u); lv=getv(v);
//printf("!%d %d\n", lu, lv);
if(lu==lv) printf("%lld\n", bef=min(u, v));
else if(L[lu]<=L[lv] && R[lv]<=R[lu]) printf("%lld\n", bef=u);
else if(L[lv]<=L[lu] && R[lu]<=R[lv]) printf("%lld\n", bef=v);
else
{
int w=lca(lu, lv);
//printf("WOW %d\n", w);
printf("%lld\n", bef=A[w-N-1]);
}
}
}
Compilation message
Main.cpp: In member function 'void SEG::update(int, int, int, int, int, pii)':
Main.cpp:49:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In member function 'void SEG::init(int, int, int)':
Main.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In member function 'int SEG::query(int, int, int, int, int)':
Main.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In member function 'int SEG::query2(int, int, int, int, int)':
Main.cpp:78:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In function 'int level(ll)':
Main.cpp:89:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int mid=lo+hi>>1;
| ~~^~~
Main.cpp: In function 'int getv(ll)':
Main.cpp:113:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
113 | int mid=lo+hi>>1;
| ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:142:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
142 | int mid=lo+hi>>1;
| ~~^~~
Main.cpp:151:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
151 | int mid=lo+hi>>1;
| ~~^~~
Main.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
126 | scanf("%d%d%d", &N, &Q, &T);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:127:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:193:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
193 | scanf("%lld%lld", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
989 ms |
155772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
989 ms |
155772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
989 ms |
155772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4093 ms |
154324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
