311. Ice-cream TycoonTime limit per test: 3 second(s)
Memory limit: 65536 kilobytesinput: standard
output: standard<\/p>\n
You’ve recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers.<\/p>\n
The day is described with a sequence of queries. Each query can be eitherARRIVE n<\/em> c<\/em>, meaning that a supplier has delivered n<\/em> pieces of ice-cream pricedc<\/em> each to you, or BUY n<\/em> t<\/em>, meaning that a student wants to buy n<\/em> pieces of ice-cream, having a total of t<\/em> money. The latter is processed as follows: in casen<\/em> cheapest pieces of ice-cream you have cost no more than t<\/em> (together), you sell those n<\/em> cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream.<\/p>\n For each student, output HAPPY if she gets her ice-cream, and UNHAPPYif she doesn’t.<\/p>\n Input<\/strong>The input file contains between 1 and 105<\/sup> queries (inclusive), each on a separate line. The queries are formatted as described above, either ARRIVE n<\/em> c<\/em>or BUY n<\/em> t<\/em>, 1 \u2264 n<\/em>, c<\/em> \u2264 106<\/sup>, 1 \u2264 t<\/em> \u2264 1012<\/sup>.<\/p>\n Output<\/strong>For each BUY-query output one line, containing either the word HAPPY or the word UNHAPPY (answers should be in the same order as the corresponding queries).<\/p>\n Example(s)<\/strong> sample input sample output ARRIVE 1 1 311. Ice-cream TycoonTime limit per test: 3 second(s)Memory limit: 65536 kilobytesinput: standardoutput: standard You’ve recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/354"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=354"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/354\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=354"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000 HAPPY
UNHAPPY
HAPPY
\u8fd9\u4e2a\u9898\u76ee\u4e00\u770b\u5c31\u662f\u88f8\u7684\u7ebf\u6bb5\u6811\u56e7\u3002\u3002\u5c31\u662f\u8001TLE\u7011\u5e03\u6c57\u3002\u3002\u3002\u8fd9\u6b21\u6211\u706b\u4e86\u3002\u3002\u5199\u4e86\u4e2a\u5e26\u6807\u8bb0\u7684\u975e\u9012\u5f52
\u7ebf\u6bb5\u6811\u7ec8\u4e8eA\u4e86\u5185\u6d41\u6ee1\u9762\u56e7\u3002\u3002\u3002
Code\uff1a
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxc=1<<20;
using namespace std;
typedef long long ll;
char cmd[100];
#define scan(t)
{
char pt;
while(pt=getchar(),pt<‘0’||pt>’9’);
t=pt-‘0’;
while(pt=getchar(),pt>=’0’&&pt<=’9′)t=t*10+pt-‘0’;
}
bool Mark[1<<21];
ll sum[1<<21]={},num[1<<21]={};
void set(int t)
{
sum[t]=sum[t*2]+sum[t*2+1];
num[t]=num[t*2]+num[t*2+1];
}
void MarkIt(int t)
{
sum[t]=num[t]=0;
Mark[t]=true;
}
void PushDown(int t)
{
if(Mark[t])
MarkIt(t*2),MarkIt(t*2+1);
Mark[t]=false;
}
void Update(int t,ll c)
{
int i,l,r;
for(i=1,l=0,r=maxc;i<maxc;)
{
PushDown(i);i<<=1;
int m=l+r>>1;
if(t>=m)i++,l=m;
else r=m;
}
i=t+maxc;sum[i]+=t*c;num[i]+=c;
for(i>>=1;i;i>>=1)set(i);
}
ll get(int n)
{
if(num[1]<n)return -1;
ll ret=0;int i;
for(i=1;i<maxc;)
{
PushDown(i);i<<=1;
if(num[i]>=n)continue;
ret+=sum[i];n-=num[i];i++;
}
return ll(n)*(i-maxc)+ret;
}
void clear(int n)
{
int i;
for(i=1;i<maxc;)
{
PushDown(i);i<<=1;
if(num[i]>=n)continue;
n-=num[i];MarkIt(i);i++;
}
Update(i-maxc,-n);
}
int main()
{
\/\/freopen("in","r",stdin);
int n;ll c;
while(scanf("%s",cmd)==1)
{
scan(n);scan(c);
if(cmd[0]==’A’)Update(c,n);
else
{
ll tmp=get(n);
if(tmp==-1||tmp>c)
puts("UNHAPPY");
else
puts("HAPPY"),clear(n);
}
}
} <\/p>\n","protected":false},"excerpt":{"rendered":"