http://www.lydsy.com/JudgeOnline/problem.php?id=1568
写多了就觉着水了。。。
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 double a[N<<],b[N<<]; bool have[N<<]; long long ans; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void change(int k,int l,int r,double A,double B)
{
if(!have[k])
{
have[k]=true;
a[k]=A;
b[k]=B;
return;
}
if(l==r)
{
a[k]=max(a[k],A);
return;
}
else
{
if(A>a[k]+(r-l)*b[k])
{
a[k]=A;
b[k]=B;
return;
}
if(a[k]>A+(r-l)*B) return;
int mid=l+r>>;
if(A<a[k])
{
if(A+(mid-l)*B>a[k]+(mid-l)*b[k])
{
change(k<<,l,mid,a[k],b[k]);
a[k]=A;
b[k]=B;
}
else change(k<<|,mid+,r,A+(mid+-l)*B,B);
}
else
{
if(A+(mid-l)*B>a[k]+(mid-l)*b[k])
{
change(k<<|,mid+,r,a[k]+(mid+-l)*b[k],b[k]);
a[k]=A;
b[k]=B;
}
else change(k<<,l,mid,A,B);
}
}
} void query(int k,int l,int r,int p)
{
if(!have[k]) return;
if(l==r)
{
ans=max(ans,(long long)a[k]);
return;
}
ans=max(ans,(long long)(a[k]+(p-l)*b[k]));
int mid=l+r>>;
if(p<=mid) query(k<<,l,mid,p);
else query(k<<|,mid+,r,p);
} int main()
{
int n,x;
char c[];
double s,p;
read(n);
while(n--)
{
scanf("%s",c);
if(c[]=='Q')
{
read(x);
ans=;
query(,,N-,x);
cout<<ans/<<'\n';
}
else
{
scanf("%lf%lf",&s,&p);
change(,,N-,s,p);
}
}
}
1568: [JSOI2008]Blue Mary开公司
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 1706 Solved: 593
[Submit][Status][Discuss]
Description
Input
第一行 :一个整数N ,表示方案和询问的总数。
接下来N行,每行开头一个单词“Query”或“Project”。
若单词为Query,则后接一个整数T,表示Blue Mary询问第T天的最大收益。
若单词为Project,则后接两个实数S,P,表示该种设计方案第一天的收益S,以及以后每天比上一天多出的收益P。
1 <= N <= 100000 1 <= T <=50000 0 < P < 100,| S | <= 10^6
提示:本题读写数据量可能相当巨大,请选手注意选择高效的文件读写方式。
Output
对于每一个Query,输出一个整数,表示询问的答案,并精确到整百元(以百元为单位,
例如:该天最大收益为210或290时,均应该输出2)。没有方案时回答询问要输出0
Sample Input
10
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000
Sample Output
0
0
0
0
0
0
0
0
0