#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define ll long long
const int N = 3e5;
const int T = 20;
int n, m, t;
ll mod;
ll a[N];
int lca[N][T];
int up[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(ll a)
{
int l = -1, r = n;
while(r - l > 1)
{
ll midd = (r + l) / 2;
if((midd + 2) * (midd + 1) / 2 <= a)
{
l = midd;
}
else
{
r = midd;
}
}
return {l + 1, a - 1LL * (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 t2 = go_to2(v -> right, (r + l) / 2 + 1, r, x);
if(t2 != -1)
{
return t2;
}
int t1 = go_to2(v -> left, l, (r + l) / 2, x);
return t1;
}
int coun(node* v, int l, int r, int x)
{
if(x < l)
{
return 0;
}
if(r <= x)
{
return v -> _sz;
}
return coun(v -> left, l, (r + l) / 2, x) + coun(v -> right, (r + l) / 2 + 1, r, x);
}
ll query(ll a, ll 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);
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);
if(t.Y > t1.Y)
{
swap(t.Y, t1.Y);
}
//cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
if(t.Y == t1.Y)
{
t.Y = coun(mass[t.X], 0, n, t.Y - 1);
return t.Y + 1 + 1LL * t.X * (t.X + 1) / 2;
}
for(int j = T - 1; j >= 0; j--)
{
if(lca[t1.Y][j] > t.Y)
{
t1.Y = lca[t1.Y][j];
}
}
t.X = up[t1.Y];
t.Y = coun(mass[t.X], 0, n, t.Y - 1);
return t.Y + 1 + 1LL * (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()
{
// ifstream cin("input1.txt.4c");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> t;
// cout << n << "\n";
mod = 1LL * (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] -= 1LL * i * (i + 1) / 2;
int u1 =go_to(mass[i + 1], 0, n, a[i] - 1);
int u = go_to(mass[i + 1], 0, n, a[i]);
lca[u][0] = u1;
up[u] = i;
mass[i] = new node();
go_to1(mass[i + 1], mass[i], 0, n, u);
}
for(int j = 1; j < T; j++)
{
for(int i = 0; i <= n; i++)
{
lca[i][j] = lca[lca[i][j - 1]][j - 1];
}
}
ll z = 0;
for(int i = 0; i < m; i++)
{
ll a, b;
cin >> a >> b;
a = (a - 1 + 1LL * t * z) % mod;
b = (b - 1 + 1LL * t * z) % mod;
cout << (z = query(a, b)) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
449 ms |
149348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
449 ms |
149348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
449 ms |
149348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1688 ms |
149996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
