#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;
const int N = 2e5 + 500;
int root[N], le[N * 100], ri[N * 100];
vector <int> t;
ll a[N];
ll last;
int n, q, tt;
int make(int x) {
int v = sz(t);
t.pb(t[x]);
le[v] = le[x];
ri[v] = ri[x];
return v;
}
void build(int v, int l, int r) {
t[v] = r - l + 1;
if (l == r) {
return;
}
int md = (l + r) >> 1;
t.pb(0); le[v] = v * 2 + 1;
t.pb(0); ri[v] = v * 2 + 2;
build(v * 2 + 1, l, md);
build(v * 2 + 2, md + 1, r);
}
void upd(int v, int l, int r, int ps) {
if (l == r) {
t[v] = 0;
return;
}
else {
t[v]--;
int md = (l + r) >> 1;
if (t[le[v]] < ps) {
ri[v] = make(ri[v]);
upd(ri[v], md + 1, r, ps - t[le[v]]);
}
else {
le[v] = make(le[v]);
upd(le[v], l, md, ps);
}
}
}
int sum(int v, int l, int r, int tl, int tr) {
if (l == tl && r == tr) {
return t[v];
}
if (l > r || tl > tr || l > tr || tl > r) {
return 0;
}
int md = (l + r) >> 1;
return sum(le[v], l, md, tl, min(md, tr)) +
sum(ri[v], md + 1, r, max(md + 1, tl), tr);
}
int getid(int v, int l, int r, int ps) {
if (l == r) {
return l;
}
else {
int md = (l + r) >> 1;
if (t[le[v]] < ps) {
return getid(ri[v], md + 1, r, ps - t[le[v]]);
}
else {
return getid(le[v], l, md, ps);
}
}
}
pair <ll, ll> get_id(ll x) {
int l = 1;
int r = n + 1;
while (l < r) {
int md = (l + r + 1) >> 1;
if (md * 1ll * (md - 1) / 2ll < x) {
l = md;
}
else {
r = md - 1;
}
}
return {l, x - (l * 1ll * (l - 1) / 2ll)};
}
int main()
{
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("toys.in");
// out("toys.out");
// in("input.txt");
// out("output.txt");
// cerr.precision(9); cerr << fixed;
// clock_t tStart = clock();
cin >> n >> q >> tt;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
root[n + 1] = 0;
t.pb(0);
build(0, 1, n + 1);
for (int i = n; i >= 1; i--) {
root[i] = make(root[i + 1]);
ll id = a[i] - (i * 1ll * (i - 1) / 2ll) + 1;
upd(root[i], 1, n + 1, id);
}
last = 0;
ll MAXN = (n + 1) * 1ll * (n + 2) / 2ll;
while (q--) {
ll x, y;
cin >> x >> y;
x = (x - 1 + tt * last) % MAXN + 1;
y = (y - 1 + tt * last) % MAXN + 1;
pair <ll, ll> nx = get_id(x);
pair <ll, ll> ny = get_id(y);
int ft = getid(root[nx.F], 1, n + 1, nx.S), sd = getid(root[ny.F], 1, n + 1, ny.S);
int l = 1, r = min(nx.F, ny.F);
int L = min(ft, sd) + 1;
int R = max(ft, sd);
while (l < r) {
int md = (l + r + 1) >> 1;
if (sum(root[md], 1, n + 1, L, R) == 0) {
l = md;
}
else {
r = md - 1;
}
}
ll ans = (l * 1ll * (l - 1) / 2ll);
ans += sum(root[l], 1, n + 1, 1, ft);
last = ans;
cout << ans << el;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
3820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
3820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
3820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
3820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
