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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include <bits/stdc++.h>
using namespace std;
#define y1 y$$$$
#define y0 y_$_$
const double eps = 1e-9;
const int N = 1e5 + 10;
const int MOD1 = 39989;
const int MOD2 = 1e9;
const int tree_size = 4e4 + 10;
struct LINE {
double k, b;
LINE(double k = 0.0, double b = 0.0): k(k), b(b) {}
} line[N];
int cmp(double x, double y) {
if (x - y > eps) return 1;
else if (y - x > eps) return -1;
else return 0;
}
double calc(int line_num, int x) {
return line[line_num].k * x + line[line_num].b;
}
int cnt;
void add(int x0, int y0, int x1, int y1) {
++cnt;
if (x0 == x1) line[cnt] = LINE(0, max(y0, y1));
else {
double k = 1.0 * (y1 - y0) / (x1 - x0);
line[cnt] = LINE(k, y0 - k * x0);
}
}
#define ls(x) x<<1
#define rs(x) x<<1|1
class SegmentTree {
struct node {
int l, r;
int maxLine;
node(int l = 0, int r = 0, int maxLine = 0): l(l), r(r), maxLine(maxLine) {}
};
int get_cmp(int id1, int id2, int x) {
return cmp(calc(id1, x), calc(id2, x));
}
node *tree;
public:
SegmentTree(int _size) {
tree = new node[_size]();
}
void Build(int l, int r, int pos) {
tree[pos] = node(l, r, 0);
if (l == r) return;
int mid = (l + r) >> 1;
Build(l, mid, ls(pos));
Build(mid + 1, r, rs(pos));
}
void UpdateLine(int l, int r, int pos, int id) {
int mid = (l + r) >> 1;
if (get_cmp(id, tree[pos].maxLine, mid) == 1)swap(id, tree[pos].maxLine);
int cmpl = get_cmp(id, tree[pos].maxLine, l);
int cmpr = get_cmp(id, tree[pos].maxLine, r);
if (cmpl == 1 || (!cmpl && id < tree[pos].maxLine)) UpdateLine(l, mid, ls(pos), id);
if (cmpr == 1 || (!cmpr && id < tree[pos].maxLine)) UpdateLine(mid + 1, r, rs(pos), id);
}
void Update(int l, int r, int pos, int id) {
if (tree[pos].l >= l && tree[pos].r <= r) return (void) UpdateLine(tree[pos].l, tree[pos].r, pos, id);
int mid = (tree[pos].l + tree[pos].r) >> 1;
if (l <= mid) Update(l, r, ls(pos), id);
if (r > mid) Update(l, r, rs(pos), id);
}
pair<double, int>pmax(pair<double, int>x, pair<double, int>y) {
if (cmp(x.first, y.first) == 1) return x;
else if (cmp(x.first, y.first) == -1) return y;
else return x.second < y.second ? x : y;
}
pair<double, int>query(int pos, int x) {
if (tree[pos].l > x || tree[pos].r < x) return {0, 0};
double res = calc(tree[pos].maxLine, x);
if (tree[pos].l == tree[pos].r) return {res, tree[pos].maxLine};
return pmax({res, tree[pos].maxLine}, pmax(query(ls(pos), x), query(rs(pos), x)));
}
};
SegmentTree tree(tree_size * 4);
int n, op, x0, x1, y0, y1;
int lastans;
int k;
signed main() {
cin >> n;
tree.Build(1, MOD1, 1);
while (n--) {
cin >> op;
if (op == 0) {
cin >> k;
k = (k + lastans - 1) % MOD1 + 1;
cout << (lastans = tree.query(1, k).second) << endl;
} else {
cin >> x0 >> y0 >> x1 >> y1;
x0 = (x0 + lastans - 1) % MOD1 + 1;
x1 = (x1 + lastans - 1) % MOD1 + 1;
y0 = (y0 + lastans - 1) % MOD2 + 1;
y1 = (y1 + lastans - 1) % MOD2 + 1;
if (x0 > x1) swap(x0, x1), swap(y0, y1);
add(x0, y0, x1, y1);
tree.Update(x0, x1, 1, cnt);
}
}
}
|