#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
//var
LL T;
template<class T>
struct node {
node* l;
node* r;
T val = T(0);
node(T val) : l(nullptr), r(nullptr), val(val) {}
node(node* l, node* r) : l(l), r(r), val(0) {
if (l) val += l->val;
if (r) val += r->val;
}
};
template<class T>
struct sex {
LL nVal = 0;
node<T>* build(vector<T>& a, int zl, int zr) {
if (zl == zr) return new node<T>(a[zl - 1]);
int m = (zl + zr) >> 1;
return new node<T>(build(a, zl, m), build(a, m + 1, zr));
}
node<T>* build(vector<T>& a) {
this->nVal = (int)a.size();
return build(a, 1, (int)a.size());
}
node<T>* build(int n) {
this->nVal = n;
vector<T> res(n, 0);
return build(res, 1, n);
}
node<T>* upd(node<T>* c, int zl, int zr, const int& pos, const T& new_val) {
//debug(c->val, zl, zr, pos, new_val);
if (zl == zr) {
//debug(zl, new_val);
return new node<T>(new_val);
}
int m = (zl + zr) >> 1;
if (pos <= m)
return new node<T>(upd(c->l, zl, m, pos, new_val), c->r);
else
return new node<T>(c->l, upd(c->r, m + 1, zr, pos, new_val));
}
T query(node<T>* c, int zl, int zr, int l, int r) {
if (c == nullptr || l > r)
return T(0);
if (l <= zl && zr <= r)
return c->val;
int m = (zl + zr) >> 1;
T ret = query(c->l, zl, m, l, min(r, m)) +
query(c->r, m + 1, zr, max(l, m + 1), r);
return ret;
};
int walk(node<T>* c, int zl, int zr, T quota) {
if (c == nullptr || c->val < quota)
return -1;
if (zl == zr) return zl;
int m = (zl + zr) >> 1;
T onLeft = c->l->val;
//debug(zl, zr, quota, c->val, onLeft);
if (quota <= onLeft) return walk(c->l, zl, m, quota);
else return walk(c->r, m + 1, zr, quota - onLeft);
};
int walk(node<T>* c, T quota) { return walk(c, 1, nVal, quota); }
T query(node<T>* c, int l, int r) { return query(c, 1, nVal, l, r); }
};
void solve() {
LL n, q, t;
cin >> n >> q >> t;
vector<int> bottom(n + 1, 1);
sex<int> tree;
node<int>* ptr = tree.build(bottom);
vector<node<int>*> roots(n + 1, ptr);
vector<int> a(n);
for (auto& u : a)
cin >> u;
//debug(tree.walk(roots[n], 4));
for (int level = n - 1; level >= 0; level--) {
int withTwo = a[level] - ((level) * (level + 1)) / 2;
int toZero = tree.walk(roots[level + 1], withTwo + 1);
assert(toZero != -1);
roots[level] = tree.upd(roots[level + 1], 1, n + 1, toZero, 0);
//debug(tree.query(roots[level], 1, n + 1));
}
vector<LL> lt(n + 1);
FOR (i, n) {
lt[i] = ((LL)(i) * (i + 1)) / 2;
}
//debug(lt);
//debug(roots);
LL pans = 0;
while (q--) {
int x, y;
cin >> x >> y;
x = ((x - 1) + t * pans) % (((n + 1) * (n + 2))/2) + 1;
y = ((y - 1) + t * pans) % (((n + 1) * (n + 2))/2) + 1;
int lx = lower_bound(all(lt), x) - lt.begin() - 1;
int ly = lower_bound(all(lt), y) - lt.begin() - 1;
//debug(lx, ly);
if (lx < ly) {
//force lx deeper
swap(lx, ly);
swap(x, y);
}
int ix = x - lt[lx], iy = y - lt[ly];
int lmx = tree.walk(roots[lx], ix);
if (tree.query(roots[ly], 1, lmx) == iy) {
pans = y;
cout << y << "\n";
continue;
}
int lmy = tree.walk(roots[ly], iy);
//debug(lmx, lmy);
//debug(ix, iy);
{
//jump from lmx, lmy
auto equalJumps = [&](int jump) -> int {
int res = -1;
int jx = tree.query(roots[n - jump], 1, lmx);
int jy = tree.query(roots[n - jump], 1, lmy);
if (jx != jy) return -1;
res = jx;
res += lt[n - jump];
return res;
};
int lo = 1, hi = n, mid;
while (lo < hi) {
mid = (lo + hi) >> 1;
if (equalJumps(mid) != -1) hi = mid;
else lo = mid + 1;
}
pans = equalJumps(lo);
cout << pans << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
36216 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
36216 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
36216 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
36240 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
