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
115
116
117
118
119
120
| #include <bits/stdc++.h>
using namespace std;
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define Pair pair<double,LL>
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997
#define mod1 39989
#define mod2 1000000000
LL n,m;
struct node {
double k,b;
} line[MS];
int tli;
int p[MS<<2];
double calc(int i,int x) {
return line[i].k*x+line[i].b;
}
void push_down(int rt,int l,int r,int i) {
int m = l+r>>1;
int j = p[rt];
double ci = calc(i,m);
double cj = calc(j,m);
if(!j){
p[rt] = i;
return;
}
if(l == r) {
if(ci > cj) p[rt] = i;
return;
}
if(line[i].k > line[j].k) {
if(ci > cj) p[rt] = i ,push_down(ls,l,m,j);
else push_down(rs,m+1,r,i);
}
else if(line[i].k < line[j].k) {
if(ci > cj) p[rt] = i ,push_down(rs,m+1,r,j);
else push_down(ls,l,m,i);
}
else {
if(line[i].b > line[j].b) p[rt] = i;
}
}
void update(int L,int R,int l,int r,int rt,int i){
if(L <= l && r <= R){
push_down(rt,l,r,i);
return;
}
int m = l+r>>1;
if(m >= L) update(L,R,l,m,ls,i);
if(m < R) update(L,R,m+1,r,rs,i);
}
Pair pmax(Pair t1,Pair t2) {
if(t1.one > t2.one) return t1;
else if(t1.one < t2.one) return t2;
else return t1.two < t2.two ? t1:t2;
}
Pair get_line(int l,int r,int rt,int tar) {
if(tar < l || tar > r) return {0,0};
int m = l+r>>1;
double cc = calc(p[rt],tar);
if(l == r) return {cc,p[rt]};
return pmax({cc,p[rt]},pmax(get_line(l,m,ls,tar),get_line(m+1,r,rs,tar)));
}
int main() {
ios::sync_with_stdio(false);
int lastans = 0;
cin >> n;
while(n--) {
int op,tar;
int x1,y1,x2,y2;
cin >> op;
if(op) {
cin >> x1 >> y1 >> x2 >> y2;
x1 = (x1+lastans-1+mod1)%mod1+1;
y1 = (y1+lastans-1+mod2)%mod2+1;
x2 = (x2+lastans-1+mod1)%mod1+1;
y2 = (y2+lastans-1+mod2)%mod2+1;
if(x1 > x2) swap(x1,x2) ,swap(y1,y2);
++tli;
if(x1 == x2){
line[tli].k = 0;
line[tli].b = max(y1,y2);
}
else{
line[tli].k = 1.0*(y2-y1)/(x2-x1),
line[tli].b = y1 - line[tli].k*x1;
}
update(x1,x2,1,mod1,1,tli);
} else {
cin >> tar;
tar = (tar+lastans-1+mod1)%mod1+1;
lastans = get_line(1,mod1,1,tar).two;
cout << lastans << endl;
}
}
return 0;
}
|
