This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 200100;
const int M = 10;
const int PW = 10;
const int HPW = 233;
const int md = int(1e9) + 7;
ll n, a[N];
int q, t;
struct seg_tree{
seg_tree *l, *r;
int sm;
seg_tree(): l(0), r(0), sm(0) {}
seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}
void build(int tl, int tr){
sm = tr - tl + 1;
if (tl == tr) return;
int md = (tl + tr) >> 1;
l = new seg_tree();
r = new seg_tree();
l -> build(tl, md);
r -> build(md + 1, tr);
}
void delt(int tl, int tr, int ind){
sm--;
if (tl == tr) return;
int md = (tl + tr) >> 1;
if (l -> sm < ind){
r = new seg_tree(r);
r -> delt(md + 1, tr, ind - (l -> sm));
} else {
l = new seg_tree(l);
l -> delt(tl, md, ind);
}
}
ll get(int tl, int tr, int ql, int qr){
if (ql > qr) return 0;
if (tl == ql && tr == qr) return sm;
int md = (tl + tr) >> 1;
return (l -> get(tl, md, ql, min(qr, md))) +
(r -> get(md + 1, tr, max(md + 1, ql), qr));
}
int get_by_cnt(int tl, int tr, int ind){
if (tl == tr) return tl;
int md = (tl + tr) >> 1;
if (l -> sm < ind){
return r -> get_by_cnt(md + 1, tr, ind - (l -> sm));
} else {
return l -> get_by_cnt(tl, md, ind);
}
}
};
seg_tree *root[N];
/// 0 -- layer, 1 -- index
i2 get_id(ll x){
ll l = 1, r = n + 1;
while (l < r){
ll md = (l + r + 1) >> 1;
if (x > md * (md - 1) / 2)
l = md;
else r = md - 1;
}
return {l, x - (l * (l - 1) / 2)};
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> q >> t;
for (int i = 1; i <= n; i++)
cin >> a[i];
root[n + 1] = new seg_tree();
root[n + 1] -> build(1, n + 1);
for (int i = n; i > 0; i--){
root[i] = new seg_tree(root[i + 1]);
ll id = a[i] - (ll(i) * (ll(i) - 1ll) / 2ll);
root[i] -> delt(1, n + 1, id + 1);
}
ll last = 0;
ll BIG = (ll(n) + 1) * (ll(n) + 2) / 2ll;
for (; q; q--){
ll x, y; cin >> x >> y;
x = ((x - 1) + t * last) % BIG + 1;
y = ((y - 1) + t * last) % BIG + 1;
i2 nw_x = get_id(x);
i2 nw_y = get_id(y);
/// do binary search
int lf = 1, rt = min(nw_x[0], nw_y[0]);
int ps1 = root[nw_x[0]] -> get_by_cnt(1, n + 1, nw_x[1]);
int ps2 = root[nw_y[0]] -> get_by_cnt(1, n + 1, nw_y[1]);
int MN = min(ps1, ps2);
int MX = max(ps1, ps2);
while (lf < rt){
int md = (lf + rt + 1) >> 1;
if (root[md] -> get(1, n + 1, MN + 1, MX) == 0)
lf = md;
else rt = md - 1;
}
/// lf -- new layer
/// get new id
ll res = ll(lf) * (ll(lf) - 1ll) / 2ll;
res += root[lf] -> get(1, n + 1, 1, ps1);
last = res;
// cout << res << '\n';
cout << res << endl;
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'std::array<int, 2> get_id(ll)':
Main.cpp:93:13: warning: narrowing conversion of 'l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
93 | return {l, x - (l * (l - 1) / 2)};
| ^
Main.cpp:93:18: warning: narrowing conversion of '(x - ((l * (l - 1)) / 2))' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
93 | return {l, x - (l * (l - 1) / 2)};
| ~~^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |