bzoj5045: 打砖块

Description

小Q最近沉迷于一款新型《打砖块》游戏。在每局游戏中，呈现在屏幕上的是一堵无限大小的墙壁。墙壁上镶嵌着

无数长度为2、宽度为1的砖块。墙壁被分成若干行，每行宽度都为1，相邻两个格子形成一个砖块。相邻两行的砖

块是间隔摆放的。墙壁从下往上行编号递增，从左往右列编号递增。如下图所示：

在游戏的一开始，有n块砖块消失了。如果两块在同一行且相邻的砖块都消失了，那么玩家可以移除它们上方与它

们都相邻的那一个砖块。请写一个程序帮助小Q计算最多可以让多少个位置没有砖块。

Input

第一行包含两个正整数n(1<=n<=100000)，表示一开始消失的砖块个数。

接下来n行，每行两个整数x_i,y_i(|x_i|,|y_i|<=10^9)

分别表示每个消失的砖块的位置，即左半部分位于第x_i行第y_i列。

Output

输出一行一个整数，即没有砖块的位置个数的最大值。

从下到上扫描线，用链表维护当前哪些位置可以有砖块，每向上移一行，每个有砖块的连续段最右边的砖块消失，因此可以暴力模拟，维护一个表记录哪些点当前在连续段最右侧，在扫描线移动时删除这些点。由于一开始需要排序，时间复杂度为O(nlogn)。

#include<bits/stdc++.h>

const int N=1e5+,P=;

char ib[N*],*ip=ib;

int _(){

    int x=,f=;

    while(*ip<)*ip++=='-'?f=-:;

    while(*ip>)x=x*+*ip++-;

    return x*f;

}

struct pos{

    int x,y;

    bool operator<(const pos&w)const{return x<w.x;}

}ps[N];

int n;

struct itv{

    mutable int l,r;

    bool operator<(const itv&w)const{return l<w.l;}

};

int now=-2e9,cnt=;

struct node{

    int x;

    bool ed,in;

    node*pv,*nx;

}h[P];

node*at(int x,bool nw){

    int w=unsigned(x)%P;

    while(h[w].ed){

        if(h[w].x==x)return h+w;

        w=(w+)%P;

    }

    if(nw)return h[w].x=x,h[w].ed=,h+w;

    return ;

}

long long ans=;

node*ts[N];

int tp=;

void upd(){

    ans+=cnt;

    ++now;

    for(int i=;i<tp;++i){

        if(ts[i]->nx||!ts[i]->in)ts[i--]=ts[--tp];

        else{

            --cnt;

            ts[i]->in=;

            ts[i]=ts[i]->pv;

            if(!ts[i])ts[i--]=ts[--tp];

        }

    }

    for(int i=;i<tp;++i)ts[i]->nx=;

}

void ins(int x,int y){

    while(now<x&&cnt)upd();

    now=x;

    node*p=at(y,);

    if(p->in)return;

    p->in=;

    p->pv=p->nx=;

    ++cnt;

    node*pv=at(y-,),*nx=at(y+,);

    if(pv&&pv->in)(p->pv=pv)->nx=p;

    if(nx&&nx->in)(p->nx=nx)->pv=p;

    if(!p->nx)ts[tp++]=p;

}

int main(){

    fread(ib,,sizeof(ib),stdin);

    n=_();

    for(int i=;i<n;++i){

        int x=_(),y=_();

        ps[i]=(pos){x,(y-x)/};

    }

    std::sort(ps,ps+n);

    for(int i=;i<n;++i)ins(ps[i].x,ps[i].y);

    while(cnt)upd();

    printf("%lld\n",ans);

    return ;

}

巴特西

bzoj5045: 打砖块

Description

Input

Output

最新文章

热门文章