#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
#define int ll
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
void add(int &a, const int b) {if((a += b) >= md) a -= md;}
void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
int prod(const int a, const int b) {return ll(a) * b % md;}
};
int n, q, T;
const int N = 2e5 + 5;
ll a[N], b[N], t[N], z;
struct tree {
tree *l, *r;
int v;
tree(int tl = 0, int tr = n - 1) {
if(tl < 0) {
l = r = 0;
v = 0;
} else if(tl < tr) {
int tm = tl + tr >> 1;
l = new tree(tl, tm);
r = new tree(tm + 1, tr);
v = l->v + r->v;
} else {
l = r = 0;
v = 1;
}
}
tree(const tree *f) {memcpy(this, f, sizeof *f);}
tree *upd(int i, int tl = 0, int tr = n - 1) const {
if(tl == tr) return new tree(-1);
int tm = tl + tr >> 1;
tree *res = new tree(this);
if(i <= tm)
res->l = l->upd(i, tl, tm);
else
res->r = r->upd(i, tm + 1, tr);
res->v--;
return res;
}
int kth(int k, int tl = 0, int tr = n - 1) const {
if(tl == tr) return tl;
int tm = tl + tr >> 1;
return l->v > k
? l->kth(k, tl, tm)
: r->kth(k - l->v, tm + 1, tr);
}
int sum(int R, int tl = 0, int tr = n - 1) const {
if(tr <= R) return v;
if(tl > R) return 0;
int tm = tl + tr >> 1;
return l->sum(R, tl, tm) +
r->sum(R, tm + 1, tr);
}
};
vector<tree*> p;
void get(ll &x, int &i, int &j) {
cin >> x;
x = 1 + (x - 1 + T * z) % ((n + 1) * ll(n) >> 1);
i = upper_bound(b, b + n, x) - b - 1;
j = p[i]->kth(x - b[i]);
}
struct tree2 {
tree2 *l, *r;
int v;
tree2(int tl = 0, int tr = n - 2) {
if(tl < tr) {
int tm = tl + tr >> 1;
l = new tree2(tl, tm);
r = new tree2(tm + 1, tr);
v = min(l->v, r->v);
} else {
l = r = 0;
v = t[tl];
}
}
int get(int L, int R, int tl = 0, int tr = n - 2) const {
if(L > R) return +inf;
if(L == tl && R == tr) return v;
int tm = tl + tr >> 1;
return min(l->get(L, min(R, tm), tl, tm),
r->get(max(tm + 1, L), R, tm + 1, tr));
}
};
void solve() {
cin >> n >> q >> T; ++n;
for(ll i = 0, j = 1; i < n; ++i) {
j += i;
if(i + 1 < n)
cin >> a[i],
a[i] -= j;
b[i] = j;
}
p.assign(1, new tree());
for(int i = n - 2; ~i; --i) {
tree *rt = p.back();
int c = rt->kth(a[i]);
p.push_back(rt = rt->upd(c));
t[c] = i;
}
reverse(bnd(p));
tree2 tt {};
z = 0;
for(int i = 0; i < q; ++i) {
ll x, y;
int ix, iy, jx, jy;
get(x, ix, jx);
get(y, iy, jy);
if(jx == jy) {
z = ix < iy ? x : y;
} else {
int le = min(jx, jy);
int ri = max(jx, jy);
int v = tt.get(le, ri - 1);
assert(p[v]->sum(le) == p[v]->sum(le - 1));
z = b[v] + p[v]->sum(le);
}
cout << z << '\n';
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
#else
system("color a");
freopen("in.txt", "r", stdin);
int t; cin >> t;
while(t--)
#endif
solve();
}
Compilation message
Main.cpp: In constructor 'tree::tree(ll, ll)':
Main.cpp:43:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'tree* tree::upd(ll, ll, ll) const':
Main.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'll tree::kth(ll, ll, ll) const':
Main.cpp:66:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'll tree::sum(ll, ll, ll) const':
Main.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In constructor 'tree2::tree2(ll, ll)':
Main.cpp:94:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'll tree2::get(ll, ll, ll, ll) const':
Main.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
106 | int tm = tl + tr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
148956 KB |
Output is correct |
| 2 |
Correct |
25 ms |
11496 KB |
Output is correct |
| 3 |
Correct |
399 ms |
148700 KB |
Output is correct |
| 4 |
Correct |
206 ms |
78176 KB |
Output is correct |
| 5 |
Correct |
401 ms |
148668 KB |
Output is correct |
| 6 |
Correct |
114 ms |
44516 KB |
Output is correct |
| 7 |
Correct |
281 ms |
148828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
148956 KB |
Output is correct |
| 2 |
Correct |
25 ms |
11496 KB |
Output is correct |
| 3 |
Correct |
399 ms |
148700 KB |
Output is correct |
| 4 |
Correct |
206 ms |
78176 KB |
Output is correct |
| 5 |
Correct |
401 ms |
148668 KB |
Output is correct |
| 6 |
Correct |
114 ms |
44516 KB |
Output is correct |
| 7 |
Correct |
281 ms |
148828 KB |
Output is correct |
| 8 |
Incorrect |
216 ms |
1388 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
148956 KB |
Output is correct |
| 2 |
Correct |
25 ms |
11496 KB |
Output is correct |
| 3 |
Correct |
399 ms |
148700 KB |
Output is correct |
| 4 |
Correct |
206 ms |
78176 KB |
Output is correct |
| 5 |
Correct |
401 ms |
148668 KB |
Output is correct |
| 6 |
Correct |
114 ms |
44516 KB |
Output is correct |
| 7 |
Correct |
281 ms |
148828 KB |
Output is correct |
| 8 |
Incorrect |
216 ms |
1388 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1853 ms |
149340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
