#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N + 2))) */
#define K 100
int n;
int depth(long long i) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int d = (lower + upper) / 2;
if (i < (long long) (d + 1) * (d + 2) / 2)
upper = d;
else
lower = d;
}
return upper;
}
int *aaa[N_ * 2], sz[N_ * 2], n_;
void pul(int i) {
int l = i << 1, r = l | 1, hl, hr, h;
aaa[i] = (int *) malloc((sz[i] = sz[l] + sz[r]) * sizeof *aaa[i]);
hl = 0, hr = 0, h = 0;
while (hl < sz[l] && hr < sz[r])
if (aaa[l][hl] + hr <= aaa[r][hr])
aaa[i][h++] = aaa[l][hl++] + hr;
else
aaa[i][h++] = aaa[r][hr++];
while (hl < sz[l])
aaa[i][h++] = aaa[l][hl++] + hr;
while (hr < sz[r])
aaa[i][h++] = aaa[r][hr++];
}
void build(int *aa, int n) {
int i;
n_ = 1;
while (n_ < n + 2)
n_ <<= 1;
for (i = 0; i < n_; i++)
if (i >= n)
sz[n_ + i] = 0;
else {
aaa[n_ + i] = (int *) malloc((sz[n_ + i] = 1) * sizeof *aaa[n_ + i]);
aaa[n_ + i][0] = aa[i];
}
for (i = n_ - 1; i > 0; i--)
pul(i);
}
int lift(int i, int a) {
int lower = -1, upper = sz[i];
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (aaa[i][h] < a)
lower = h;
else
upper = h;
}
return a - upper;
}
int lift1(int l, int r, int a) {
static int qu[K];
int cnt;
cnt = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
qu[cnt++] = l++;
if ((r & 1) == 0)
a = lift(r--, a);
}
while (cnt--)
a = lift(qu[cnt], a);
return a;
}
long long lift2(int r, int a, int b) {
int l = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((r & 1) == 0) {
int i = r--, a_ = lift(i, a), b_ = lift(i, b);
if (a_ != b_)
a = a_, b = b_;
else {
while (i < n_) {
a_ = lift(i << 1 | 1, a), b_ = lift(i << 1 | 1, b);
if (a_ != b_)
a = a_, b = b_, i = i << 1 | 0;
else
i = i << 1 | 1;
}
return (long long) (i - n_) * (i - n_ + 1) / 2 + lift(i, a);
}
}
return -1;
}
int main() {
static int ii[N];
int q, t, i, j;
long long n1, ans;
scanf("%d%d%d", &n, &q, &t);
for (i = 0; i < n; i++) {
long long a;
scanf("%lld", &a), a--, ii[i] = a - (long long) i * (i + 1) / 2;
}
build(ii, n);
n1 = (long long) (n + 1) * (n + 2) / 2, ans = 0;
while (q--) {
long long x, y, tmp;
int dx, dy;
scanf("%lld%lld", &x, &y), x--, y--;
x = (x + t * ans) % n1, y = (y + t * ans) % n1;
if (x > y)
tmp = x, x = y, y = tmp;
dx = depth(x), i = x - (long long) dx * (dx + 1) / 2;
dy = depth(y), j = y - (long long) dy * (dy + 1) / 2;
j = lift1(dx, dy - 1, j);
printf("%lld\n", ans = (i == j ? (long long) dx * (dx + 1) / 2 + i : lift2(dx - 1, i, j)) + 1);
}
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:117:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d%d%d", &n, &q, &t);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:121:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%lld", &a), a--, ii[i] = a - (long long) i * (i + 1) / 2;
| ^~~~~~~~~~~~~~~~~
Main.c:129:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | scanf("%lld%lld", &x, &y), x--, y--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
33132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
33132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
33132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1376 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
