时光机TimeMachine

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
const double eps = 1e-9;
int n,m,tmp[N],ke[N],pn;
double pk[N],ans[N];
int ask[N][2];
struct Point{Point(double a=0,double b=0):x(a),y(b){}double x,y;}data[N];
Point operator-(const Point&a,const Point&b){return Point(a.x-b.x,a.y-b.y);}
double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
double calck(Point a,Point b){return 1.*(b.y-a.y)/(b.x-a.x);}
double calcm(Point a,double k){return -k*a.x + a.y;}
bool better(Point a,Point b,Point c){return Cross(a-b,b-c)>=0;}
bool dcmp(double a,double b){return fabs(a-b)<=eps;}
bool pcmp(int A,int B){
	Point &a=data[A],&b=data[B];
	return dcmp(a.x,b.x)?a.y>b.y:a.x<b.x;
}
bool cmpk(double a,double b){return a>b;}
deque<int>dui;
int solve(int l=1,int r=n){
	if(l==r){
		if(ask[l][0] == 0)return 0;
		ke[l]=ask[l][1];
		pk[l]=1e50;
		return 1;
	}
	int mid = (l+r)/2,len[2],i,j,re=0;
	len[0] = solve(l,mid);len[1] = solve(mid+1,r);
	for(i=mid+1;i<=r;i++)
	if(ask[i][0]==0){
		j = lower_bound(pk+l,pk+l+len[0],1-ask[i][1],cmpk)-pk-1;
		double atmp=calcm(data[ke[j]],1-ask[i][1]);
		if(atmp > ans[i])ans[i] = atmp;
	}
	//merge
	merge(ke+l,ke+l+len[0],ke+(mid+1),ke+(mid+1)+len[1],tmp+1,pcmp);
	for(i=1;i<=len[0]+len[1];i++)
	if(i==1||dcmp(data[tmp[i]].x,data[tmp[i-1]].x)==0){
		int now = tmp[i];
		while((j=dui.size())>1 && better(data[dui[j-2]],data[dui[j-1]],data[now]))dui.pop_back();
		dui.push_back(now);
	}
	while(!dui.empty()){
		int p = (++re)+l-1;
		ke[p] = dui.front();dui.pop_front();
		if(re-1>=1)pk[p] = calck(data[ke[p-1]],data[ke[p]]);
		else pk[p] = 1e50;
	}
	return re;
}
int main(){
	int i,j,a;char opt[20];
	double fa,fb;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%s",opt+1);
		switch(opt[1]){
			case'Q':
				scanf("%d",&a);
				ask[i][0] = 0;ask[i][1] = a;
			break;
			case'P':
				scanf("%lf%lf",&fa,&fb);
				data[++pn] = Point(fb,fa);
				ask[i][0] = 1;ask[i][1] = pn;
			break;
		}
	}
	solve();
	for(i=1;i<=n;i++)
	if(ask[i][0]==0){
		printf("%d\n",(int)((ans[i]+eps)/100));
	}
	return 0;
}