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
105
106
107
108
109
110
111
112
113
114
| #include<bits/stdc++.h>
using namespace std;
const int MAXx = 39989;
const int MAXy = 1e9;
const int MAXm = 1e5;
const double NINF = -2e9;
const double EPS = 1e-8;
template <typename T>
inline void read(T &a) {
char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
read(a), read(argv...);
}
inline int sig(double x) {
if (x < -EPS) return -1;
else if (x > EPS) return 1;
else return 0;
}
struct Point {
double v; int idx;
inline bool operator<(const Point sec) const {
if (sig(v - sec.v)) return v < sec.v;
else return idx > sec.idx;
}
};
inline Point max(Point fir, Point sec) {
return (fir < sec) ? sec : fir;
}
struct Stra {
double b, k; int idx;
inline Point calc(int p) {
if (idx == 0) return Point{NINF, 0};
else return Point{b + k * p, idx};
}
};
#define ls (id << 1)
#define rs (id << 1 | 1)
const int MAXnd = MAXx * 4;
int le[MAXnd + 10], ri[MAXnd + 10], mid[MAXnd + 10];
Stra stra[MAXnd + 10];
void build(int id, int l, int r) {
le[id] = l;
ri[id] = r;
mid[id] = (l + r) >> 1;
if (le[id] != ri[id]) {
build(ls, le[id], mid[id]);
build(rs, mid[id] + 1, ri[id]);
}
}
void modify(int id, int l, int r, Stra s) {
if (le[id] >= l && ri[id] <= r) {
if (stra[id].calc(mid[id]) < s.calc(mid[id])) {
swap(stra[id], s);
}
if (le[id] != ri[id]) {
if (stra[id].k < s.k) modify(rs, l, r, s);
else if (stra[id].k > s.k) modify(ls, l, r, s);
}
} else {
if (l <= mid[id]) modify(ls, l, r, s);
if (r > mid[id]) modify(rs, l, r, s);
}
}
Point query(int id, int p) {
Point ans = stra[id].calc(p);
if (le[id] != ri[id]) {
if (p <= mid[id]) ans = max(ans, query(ls, p));
else ans = max(ans, query(rs, p));
}
return ans;
}
#undef ls
#undef rs
int m;
int cnts;
int lastans;
signed main() {
build(1, 1, MAXx);
read(m);
for (int i = 1, opt, p, xa, ya, xb, yb; i <= m; ++i) {
read(opt);
if (opt == 0) {
read(p);
p = (p + lastans - 1) % MAXx + 1;
printf("%d\n", lastans = query(1, p).idx);
} else {
read(xa, ya, xb, yb);
xa = (xa + lastans - 1) % MAXx + 1;
ya = (ya + lastans - 1) % MAXy + 1;
xb = (xb + lastans - 1) % MAXx + 1;
yb = (yb + lastans - 1) % MAXy + 1;
Stra s;
if (xa > xb) {
swap(xa, xb); swap(ya, yb);
}
if (xa != xb) {
double k = (double)(yb - ya) / (double)(xb - xa);
s = Stra{ya - k * xa, k, ++cnts};
} else {
s = Stra{(double)max(ya, yb), 0, ++cnts};
}
modify(1, xa, xb, s);
}
}
return 0;
}
|
