提交记录

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define lc(x) tree[x].l
#define rc(x) tree[x].r
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define bh(x) tree[x].bh
#define md(x,y) ((x+y)>>1)
#define mod 39989
#define int long long
using namespace std;
int n,flag,k,cntbh,nowb,xa[100005],ya[100005],xb[100005],yb[100005],lastans;
double nowmax,eps=1e-15;
struct tree
{
	int l,r;
	int bh;
}tree[200005];
inline int read()
{
	int now=0,nev=1; char c=getchar();
	while(c<'0' || c>'9') { if(c=='-') nev=-1; c=getchar();}
	while(c>='0' && c<='9') { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
	return now*nev;
}
double calc(int x,int y)
{
	if(xa[x]==xb[x])
	{
		return max(ya[x],yb[x]);
	}
	return ya[x]+(double)((double)y-(double)xa[x])/double((double)xb[x]-(double)xa[x])*(double)((double)yb[x]-(double)ya[x]);
}
void build(int x,int y,int p)
{
	lc(p)=x; rc(p)=y;
	if(x==y) return;
	int mid=md(x,y);
	build(x,mid,ls(p));
	build(mid+1,y,rs(p));
}
void add(int nowbh,int p)
{
	int mid=md(lc(p),rc(p)),bhnow=nowbh;
	if(lc(p)>=xa[bhnow]&&rc(p)<=xb[bhnow])
	{
		if(calc(bhnow,mid)-calc(bh(p),mid)>eps||(abs(calc(bhnow,mid)-calc(bh(p),mid))<=eps&&bhnow<bh(p))) swap(bhnow,bh(p));
		if(calc(bhnow,lc(p))-calc(bh(p),lc(p))>eps||(abs(calc(bhnow,lc(p))-calc(bh(p),lc(p)))<=eps&&bhnow<bh(p))) add(bhnow,ls(p));
		if(calc(bhnow,rc(p))-calc(bh(p),rc(p))>eps||(abs(calc(bhnow,rc(p))-calc(bh(p),rc(p)))<=eps&&bhnow<bh(p))) add(bhnow,rs(p));
		return;
	}
	if(mid>=xa[bhnow]) add(bhnow,ls(p));
	if(mid<xb[bhnow]) add(bhnow,rs(p));
}
void ask(int x,int p)
{
	int cc=calc(bh(p),x),mid=md(lc(p),rc(p));
	if(cc-nowmax>eps||(abs(cc-nowmax)<=eps&&bh(p)<nowb)) nowmax=cc,nowb=bh(p);
	if(lc(p)==rc(p)) return;
	if(mid>=x) ask(x,ls(p));
	else ask(x,rs(p));
}
signed main()
{
	n=read();
	xa[0]=0;
	xb[0]=39989;
	ya[0]=0;
	yb[0]=0;
	build(1,39989,1);
	for(int i=1;i<=n;i++)
	{
		flag=read();
		if(flag==0)
		{
			nowmax=0; nowb=0;
			k=(read()+lastans-1)%mod+1;
			ask(k,1);
			printf("%d\n",nowb);
			lastans=nowb;
		}
		else
		{
			cntbh++;
			xa[cntbh]=(read()+lastans-1)%mod+1; ya[cntbh]=(read()+lastans-1)%1000000000+1;
			xb[cntbh]=(read()+lastans-1)%mod+1; yb[cntbh]=(read()+lastans-1)%1000000000+1;
			if(xa[cntbh]>xb[cntbh])
			{
				swap(xa[cntbh],xb[cntbh]);
				swap(ya[cntbh],yb[cntbh]);
			}
			add(cntbh,1);
		}
	}
}