【bzoj1568】JSOI2008—BlueMary开公司

// bzoj1568
#include
#include
#include
#include
#include
#include
#define LL long long
#define inf (1ll<<60)
#define eps 1e-8
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
	
const int lim=50000,maxn=100010;
int n;
char ch[100];

struct seg {
	double k,b;
	double ch(int x) {return k*x+b;}
}t;
struct node {int cov;seg mx;}tr[maxn<<2];

double X(seg a,seg b) {
	return fabs(a.k-b.k)>1;
	if (!tr[k].cov) tr[k].cov=1,tr[k].mx=g;
	else {
		seg a1=g,a2=tr[k].mx;double x=X(a1,a2);
		if (a1.ch(l)=r) {tr[k].mx=a1;return;}
		if (x<=mid) tr[k].mx=a2,insert(k<<1,l,mid,a1);
		else tr[k].mx=a1,insert(k<<1|1,mid+1,r,a2);
	}
}
double query(int k,int l,int r,int x) {
	if (l==r) return tr[k].cov ? tr[k].mx.ch(x) : 0;
	int mid=(l+r)>>1;double t;
	if (x<=mid) t=query(k<<1,l,mid,x);
	else t=query(k<<1|1,mid+1,r,x);
	return tr[k].cov ? max(t,tr[k].mx.ch(x)) : t;
}

int main() {
	scanf("%d",&n);
	for (int x,i=1;i<=n;i++) {
		scanf("%s",ch);
		if (ch[0]=='P') scanf("%lf%lf",&t.b,&t.k),insert(1,0,lim,t);
		if (ch[0]=='Q') scanf("%d",&x),printf("%lld\n",(LL)query(1,0,lim,x-1)/100);
	}
	return 0;
}