#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define int long long
const int N = 3e5;
const int T = 20;
int n, m, t;
int mod;
int a[N];
struct node{
node* left;
node* right;
int _sz;
node(){};
};
node* mass[N];
int go_to(node* v, int l, int r, int d)
{
if(l == r)
{
return l;
}
if(v -> left -> _sz <= d)
{
return go_to(v -> right, (r + l) / 2 + 1, r, d - v -> left -> _sz);
}
return go_to(v -> left, l, (r + l) / 2, d);
}
void go_to1(node* pr, node *&v, int l, int r, int k)
{
v -> _sz = pr -> _sz;
v -> _sz--;
if(l == r)
{
return;
}
if(k <= (r + l) / 2)
{
v -> left = new node();
v -> right = pr -> right;
go_to1(pr -> left, v -> left, l, (r + l) / 2, k);
}
else
{
v -> left = pr -> left;
v -> right = new node();
go_to1(pr -> right, v -> right, (r + l) / 2 + 1, r, k);
}
}
pair <int, int> funct(int a)
{
int l = -1, r = n;
while(r - l > 1)
{
int midd = (r + l) / 2;
if((midd + 2) * (midd + 1) / 2 <= a)
{
l = midd;
}
else
{
r = midd;
}
}
return {l + 1, a - (l + 2) * (l + 1) / 2};
}
int go_to2(node* v, int l, int r, int x)
{
if(!v -> _sz)
{
return -1;
}
if(l > x)
{
return -1;
}
if(l == r)
{
return l;
}
if(r <= x)
{
if(v -> right -> _sz)
{
return go_to2(v -> right, (r + l) / 2 + 1, r, x);
}
return go_to2(v -> left, l, (r + l) / 2, x);
}
int t1 = go_to2(v -> left, l, (r + l) / 2, x);
int t2 = go_to2(v -> right, (r + l) / 2 + 1, r, x);
if(t2 != -1)
{
return t2;
}
return t1;
}
int query(int a, int b)
{
pair <int, int> t = funct(a);
pair <int, int> t1 = funct(b);
t.Y = go_to(mass[t.X], 0, n, t.Y);
t1.Y = go_to(mass[t1.X], 0, n, t1.Y);
// cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
if(t.X > t1.X)
{
swap(t, t1);
}
t.Y = go_to2(mass[t.X], 0, n, t.Y);
t1.Y = go_to2(mass[t.X], 0, n, t1.Y);
// cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
t.Y = go_to2(mass[t.X], 0, n, t.Y);
t1.Y = go_to2(mass[t.X], 0, n, t1.Y);
//cout << t.Y << " " << t1.Y << "\n";
for(int j = T - 1; j >= 0; j--)
{
if(t.Y == t1.Y)
{
break;
}
// cout << j << "\n";
if((1 << j) <= t.X && go_to2(mass[t.X - (1 << j)], 0, n, t.Y) != go_to2(mass[t.X - (1 << j)], 0, n, t1.Y))
{
t.Y = go_to2(mass[t.X - (1 << j)], 0, n, t.Y);
t1.Y = go_to2(mass[t.X - (1 << j)], 0, n, t1.Y);
t.X -= (1 << j);
}
}
// cout << t.X << " " << t.Y << " " << t1.Y << "\n";
if(t.Y != t1.Y)
{
t.X--;
t.Y = go_to2(mass[t.X], 0, n, t.Y);
}
return t.Y + 1 + (t.X) * (t.X + 1) / 2;
}
void build(node* &v, int l, int r)
{
v -> _sz = r - l + 1;
if(l == r)
{
return;
}
v -> left = new node();
v -> right = new node();
build(v -> left, l, (r + l) / 2);
build(v -> right, (r + l) / 2 + 1, r);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> t;
mod = (n + 1) * (n + 2) / 2;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
mass[n] = new node();
build(mass[n], 0, n);
//cout << "A\n";
for(int i = n - 1; i >= 0; i--)
{
a[i] -= i * (i + 1) / 2;
int u = go_to(mass[i + 1], 0, n, a[i]);
mass[i] = new node();
go_to1(mass[i + 1], mass[i], 0, n, u);
}
int z = 0;
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
a = (a - 1 + t * z) % mod;
b = (b - 1 + t * z) % mod;
//cout << a << " " << b << " ";
cout << (z = query(a, b)) << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
369 ms |
135252 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
10152 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
369 ms |
135252 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
10152 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
369 ms |
135252 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
10152 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4101 ms |
137340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
