#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 _ <<' '<<
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(tree *f) {memcpy(this, f, sizeof *f);}
tree *upd(int i, int tl = 0, int tr = n - 1) {
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 = res->l->v + res->r->v;
return res;
}
int kth(int k, int tl = 0, int tr = n - 1) {
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) {
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) {
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 - 1; ++i) {
j += i;
cin >> a[i];
a[i] -= j;
b[i] = j;
}
b[n - 1] = n * ll(n - 1) / 2 + 1;
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;
}
tree2 tt {};
reverse(bnd(p));
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 {
if(jx > jy) swap(jx, jy),
swap(ix, iy),
swap(x, y);
int v = tt.get(jx, jy - 1);
z = b[v] + p[v]->sum(jx);
}
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(int, int)':
Main.cpp:42:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'tree* tree::upd(int, int, int)':
Main.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'int tree::kth(int, int, int)':
Main.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'int tree::sum(int, int, int)':
Main.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In constructor 'tree2::tree2(int, int)':
Main.cpp:93:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'int tree2::get(int, int, int, int)':
Main.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int tm = tl + tr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
148700 KB |
Output is correct |
| 2 |
Correct |
25 ms |
11624 KB |
Output is correct |
| 3 |
Correct |
418 ms |
151004 KB |
Output is correct |
| 4 |
Correct |
209 ms |
79328 KB |
Output is correct |
| 5 |
Correct |
425 ms |
150876 KB |
Output is correct |
| 6 |
Correct |
115 ms |
45132 KB |
Output is correct |
| 7 |
Correct |
287 ms |
150876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
148700 KB |
Output is correct |
| 2 |
Correct |
25 ms |
11624 KB |
Output is correct |
| 3 |
Correct |
418 ms |
151004 KB |
Output is correct |
| 4 |
Correct |
209 ms |
79328 KB |
Output is correct |
| 5 |
Correct |
425 ms |
150876 KB |
Output is correct |
| 6 |
Correct |
115 ms |
45132 KB |
Output is correct |
| 7 |
Correct |
287 ms |
150876 KB |
Output is correct |
| 8 |
Incorrect |
208 ms |
4076 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
148700 KB |
Output is correct |
| 2 |
Correct |
25 ms |
11624 KB |
Output is correct |
| 3 |
Correct |
418 ms |
151004 KB |
Output is correct |
| 4 |
Correct |
209 ms |
79328 KB |
Output is correct |
| 5 |
Correct |
425 ms |
150876 KB |
Output is correct |
| 6 |
Correct |
115 ms |
45132 KB |
Output is correct |
| 7 |
Correct |
287 ms |
150876 KB |
Output is correct |
| 8 |
Incorrect |
208 ms |
4076 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1825 ms |
153564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
