注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3463][COCI2012] Inspector  

2015-03-27 13:34:43|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3463: [COCI2012] Inspector

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 66  Solved: 17
[Submit][Status][Discuss]

Description

在一个小国家中,一个新的小镇终于建成了!如往常一样,Mirko获得了“首席税务巡查员”的职位。他的任务是保证正确地计算各公司的收入情况。一共有N家办公室坐落在主干道上,从左到右被编号为1~N。一开始,所有办公室一开始都是空的。随后,一些公司会搬入或搬出某些办公室。Mirko时不时地会经过某些办公室并审查在这些办公室中,最富有的公司的账目。

一个公司被以如下的方式描述:

T-表示搬入的第一天。

K-表示搬入的办公室的标号。

Z-公司每日的盈利。(可以是负值表示亏损)

S-公司搬入时的公司财务情况。(即公司的账户资金,也可以是负值)

如果一家公司已经在 K 办公室了,当有新公司要进入 K 办公室时,这家公司会立刻搬出。

新公司第一天并不会运营,盈利从第二天开始计算。

Mirko的审查以 3 个整数来描述:

T-审查的时间。

 B-Mirko会检查 A 办公室至 B 办公室(包括AB)之间的公司。

Mirko只会在一天结束时检查,所有公司这时已经计算完成了当天利润。

 

Input

第一行包含 2 个正整数:N1<=N<=100000)表示办公室的数量和M1<=M<=300000)表示事件的个数。

接下来 M 行,遵循以下格式:“1 T K Z S”或“2 T A B”(含义如题目描述)。其中 T 会严格递增,并且最后一天小于 1000000,Z  S 的绝对值也严格小于 1000000

(注意A可能大于B

Output

对于每次Mirko的审查,每行输出一个整数,表示当天最富有的公司的资产(可以为负)。如果Mirko经过的所有办公室中都没有公司入驻,则输出“nema”(不加引号)。

Sample Input

5 9 1 1 5 4 -5 2 2 3 5 1 3 4 6 9 2 4 1 2 1 6 2 2 3 2 8 2 1 1 9 4 0 17 2 10 5 5 2 11 1 4

Sample Output

-1 nema 7 31 17

Solution

自古大力出奇迹
将序列分成sqrt(n)块,块内维护下凸壳。插入的时候暴力重构,询问直接扫

Code

/**************************************************************
    Problem: 3463
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:20720 ms
    Memory:10656 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
char ch,B[1<<15],*S=B,*T=B,buf[1<<22],*O=buf;int aa,bb,ts,stk[20];long long prt;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
#define F(x) \
    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);\
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';x=bb?aa:-aa
void Pr(long long x){
    if(x==0)*O++='0';else{
        if(x<0)x=-x,*O++='-';
        for(ts=0;x;x/=10)stk[++ts]=x%10;
        for(;ts;*O++=stk[ts--]+48);
    }
}
#define N 100010
typedef double ld;
struct P{ld x,y;int n;}a[N],b[N];
#define PP const P&
bool operator<(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y>b.y;}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
ld operator|(PP a,PP b){return a.x*b.x+a.y*b.y;}
ld operator&(PP a,PP b){return a.x*b.y-a.y*b.x;}
ld check(PP a,PP b,PP c){return (b-a)&(c-a);}
ld zjd(PP a,PP b){return (b.y-a.y)/(a.x-b.x);}
int n,m,siz,i,t,k,z,s,l,r,op,id[N],tb[2000][30],v[N],L[N],R[N],cy;ld ans;
void vio(int l,int r){
    for(;l<=r;l++)if(v[l])ans=std::max(ans,a[l].x*t+a[l].y);
}
void add(int x){
    int i,j=0,k=id[x],r=k*siz+siz-1,*q=tb[k];
    if(r>=n)r=n-1;
    for(i=k*siz;i<=r;i++)if(v[i])b[++j]=a[i];
    std::sort(b+1,b+1+j);b[0].x=-1e100;r=0;
    for(i=1;i<=j;i++)if(b[i].x!=b[i-1].x){
        while(r>1&&check(b[q[r-1]],b[q[r]],b[i])>=0)r--;q[++r]=i;
    }
    for(i=1;i<=r;i++)q[i]=b[q[i]].n;
    L[k]=1,R[k]=r;q[0]=1;
    if(cy<r)cy=r;
}
void query(int id){
    int*q=tb[id];ld tmp;
    if(q[0]==0)return;
    for(;L[id]<R[id];L[id]++){
        tmp=zjd(a[q[L[id]]],a[q[L[id]+1]]);
        if(tmp>=t)goto outp;
    }
    outp:ans=std::max(ans,a[q[L[id]]].x*t+a[q[L[id]]].y);
}
int main(){
    scanf("%d%d\n",&n,&m);siz=sqrt(n)/3+1;
    for(i=0;i<n;i++)id[i]=i/siz;
    for(;m--;){
        F(op);F(t);
        if(op==1){
            F(k);F(z);F(s);k--;
            v[k]=1;a[k]=(P){z,s-1.0*z*t,k};
            add(k);
        }
        else{
            F(l);F(r);ans=-1e100;l--,r--;
            if(l>r)k=l,l=r,r=k;
            if(id[l]==id[r])vio(l,r);
            else{
                vio(l,id[l]*siz+siz-1);
                vio(id[r]*siz,r);
                for(i=id[l]+1;i<id[r];i++)query(i);
            }
            if(ans<-1e99)*O++='n',*O++='e',*O++='m',*O++='a';
            else prt=ans,Pr(prt);
            *O++='\n';
        }
    }
    *--O=0,puts(buf);
}
  评论这张
 
阅读(157)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018