1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 100010
#define eps 1e-6
#define INF 1000000000
using namespace std;
const int N = 39989;
int m;
struct Line {
double k, b;
};
double F(const Line &l, int x) { return x * l.k + l.b; }
#define lc i << 1
#define rc i << 1 | 1
struct Seg {
int v;
Line l;
} T[maxn * 4];
void update(int i, int l, int r, int L, int R, Line d, int v) {
if (l > R || r < L) return ; int m = l + r >> 1;
if (L <= l && r <= R) {
double tl = F(d, l), tr = F(d, r);
double sl = F(T[i].l, l), sr = F(T[i].l, r);
if (tl > sl && tr > sr) return (void) (T[i] = { v, d });
if (sl > tl && sr > tr) return ;
double tm = F(d, m), sm = F(T[i].l, m);
if (tm > sm) swap(T[i].l, d), swap(T[i].v, v);
if (d.k < T[i].l.k) update(lc, l, m, L, R, d, v);
else update(rc, m + 1, r, L, R, d, v);
return ;
}
update(lc, l, m, L, R, d, v); update(rc, m + 1, r, L, R, d, v);
}
double mx; int lans;
void query(int i, int l, int r, int k) {
if (F(T[i].l, k) > mx) mx = F(T[i].l, k), lans = T[i].v;
else if (fabs(F(T[i].l, k) - mx) < eps) lans = min(lans, T[i].v);
if (l == r) return ; int m = l + r >> 1;
if (k <= m) query(lc, l, m, k);
else query(rc, m + 1, r, k);
}
inline void solve_1() {
int x; cin >> x; x = (x + lans - 1) % N + 1;
mx = lans = 0; query(1, 1, N, x);
cout << lans << "\n";
}
int cnt;
inline void solve_2() {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
x1 = (x1 + lans - 1) % N + 1; x2 = (x2 + lans - 1) % N + 1;
y1 = (y1 + lans - 1) % INF + 1; y2 = (y2 + lans - 1) % INF + 1;
if (x1 > x2) swap(x1, x2), swap(y1, y2);
Line l; ++cnt;
if (x1 == x2) l = { 0, (double) max(y1, y2) };
else l.k = 1.0 * (y2 - y1) / (x2 - x1), l.b = y1 - l.k * x1;
update(1, 1, N, x1, x2, l, cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> m;
for (int i = 1; i <= m; ++i) {
int opt; cin >> opt;
if (opt == 0) solve_1();
else solve_2();
}
return 0;
}
|