_stOrz_ @ 2022-02-27 00:55:03
0分
#include<bits/stdc++.h>
#define mod 39989
#define mod2 1000000007
using namespace std;
char user;
int m = 4e4 + 5;
template <typename T> inline void read(T &x){
char ch = getchar(); T f = 1; x = 0;
for(; (!isdigit(ch)) and ch != '-'; ch = getchar());
if(ch == '-') f = -1, ch = getchar();
for(; isdigit(ch); x = (x << 3) + (x << 1) + ch - 48, ch = getchar());
x *= f;
}
template<typename T, typename ...Arg>void read(T &x, Arg& ...arg){
read(x);
read(arg...);
}
template <typename T>void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T, typename ...Arg> void write(T x, Arg ...arg){
write(x);
putchar(user);
write(arg...);
}
const int N = 5e5 + 5;
//---------------------------------------------------------------
struct node{
int x1, y1, x2, y2;
double k, b;
}k[N << 1];
int tree[N << 2];
//---------------------------------------------------------------
double f(int id, int x){
return k[id].k * x + k[id].b;
}
void insert(int cur, int l, int r, int s, int t, int id){
int mid = (l + r) >> 1;
if(s <= l and t >= r){
if(f(tree[cur], mid) < f(id, mid)) swap(tree[cur], id);
//cout << cur << ": " << tree[cur] << "\n";
// if(l == r) return;
if(f(tree[cur], l) < f(id, l)) insert(cur << 1, l, mid, s, t, id);
if(f(tree[cur], r) < f(id, r)) insert(cur << 1 | 1, mid + 1, r, s, t, id);
return;
}
// if(l == r) return;
if(s <= mid) insert(cur << 1, l, mid, s, t, id);
else if(t > mid) insert(cur << 1 | 1, mid + 1, r, s, t, id);
return;
}
int ask(int cur, int l, int r, int x){
if(l == r) return tree[cur];
int mid = (l + r) >> 1;
int ans = tree[cur], tmp;
if(x <= mid) { tmp = ask(cur << 1, l, mid, x); ans = (f(ans, x) > f(tmp, x) ? (ans) : (tmp)); }
else { tmp = ask(cur << 1 | 1, mid + 1, r, x); ans = (f(ans, x) > f(tmp, x) ? (ans) : (tmp)); }
return ans;
}
//---------------------------------------------------------------
signed main(signed agrc, char const *argv[]){
//---------------------------------------------------------------
int n, last, i = 0; read(n);
for(int qq = 1; qq <= n; qq++){
int opt; read(opt);
if(opt == 1){
i++;
read(k[i].x1, k[i].y1, k[i].x2, k[i].y2);
k[i].x1 = (k[i].x1 + last - 1) % mod + 1, k[i].x2 = (k[i].x2 + last - 1) % mod + 1;
k[i].y1 = (k[i].y1 + last - 1) % mod2 + 1, k[i].y2 = (k[i].y2 + last - 1) % mod2 + 1;
if(k[i].x1 > k[i].x2) swap(k[i].x1, k[i].x2), swap(k[i].y1, k[i].y2);
if(k[i].x1 == k[i].x2) k[i].k = 0, k[i].b = max(k[i].y1, k[i].y2);
else {
k[i].k = 1.0 * (double)((k[i].y1 - k[i].y2) / (k[i].x1 - k[i].x2));
k[i].b = 1.0 * (k[i].y1 - k[i].x1 * 1.0 * k[i].k);
}
insert(1, 1, m, k[i].x1, k[i].x2, i);
}
else{
int x; read(x);
x = (x + last - 1) % mod + 1; last = ask(1, 1, m, x);
write(last); putchar('\n');
}
}
//---------------------------------------------------------------
return 0;
}100分
#include<bits/stdc++.h>
#define mod 39989
#define mod2 1000000007
using namespace std;
const int N = 5e5 + 5;
struct node{
double k, b;
}k[N << 2];
double f(int id, int x){
return k[id].k * x + k[id].b;
}
int tree[N << 3];
void insert(int cur, int l, int r, int s, int t, int x){
int mid = (l + r) >> 1;
if(s <= l and t >= r){
if(f(x, mid)>f(tree[cur], mid)) swap(tree[cur], x);
if(f(x, l)>f(tree[cur], l)) insert(cur << 1, l, mid, s, t, x);
if(f(x, r)>f(tree[cur], r)) insert(cur << 1 | 1, mid + 1, r, s, t, x);
return;
}
if(s <= mid) insert(cur << 1, l, mid, s, t, x);
if(t > mid) insert(cur << 1 | 1, mid + 1, r, s, t, x);
}
int ask(int cur, int l, int r, int x){
if(l == r) return tree[cur];
int mid = (l + r) >> 1, ans = tree[cur], tmp;
if(x <= mid) { tmp = ask(cur << 1, l, mid, x); ans = (f(ans, x)>f(tmp, x)? (ans) : (tmp)); }
else { tmp = ask(cur << 1 | 1, mid + 1, r, x); ans = (f(ans, x)>f(tmp, x) ? (ans) : (tmp)); }
return ans;
}
int main(){
int T, tot = 0, last = 0;
cin >> T;
while(T--){
int opt; cin >> opt;
if(opt == 1){
tot++;
int x0, x1, y0, y1;
cin >> x0 >> y0 >> x1 >> y1;
x0 = (x0 + last - 1) % mod + 1, y0 = (y0 + last - 1) % mod2 + 1;
x1 = (x1 + last - 1) % mod + 1, y1 = (y1 + last - 1) % mod2 + 1;
if(x0 > x1) swap(x0, x1), swap(y0, y1);
if(x0 == x1) k[tot] = ((node){0, max(y1, y0)});
else{k[tot].k = 1.0 * (y1 - y0) / (x1 - x0); k[tot].b = y1 - x1 * k[tot].k;}
insert(1, 1, 4e5 + 5, x0, x1, tot);
}
else {
int x; cin >> x;
x = (x + last - 1) % mod + 1;
last = ask(1, 1, 4e5 + 5, x);
cout << last << "\n";
}
}
}