【实验舱国庆模拟】Day3 B.Lecture

题目链接

 

题意:

  讲堂里有抬头听讲的学生,也有低头玩手机的学生。对于位置在$(x,y)$的人,如果$(x-1,y-1)$,$(x-1,y)$,$(x-1,y+1)$这三个位置都是被挡住/抬着头的人,那么这个人就会被挡住。特殊地,如果$(x-1,y-1)$,$(x-1,y)$,$(x-1,y+1)$三个位置中有一个是不存在的,那么$(x,y)$久一定不会被挡住。注意:无论有没有低头,都有可能被挡住。

  已知有$n$组抬头的人,形如$(x_i,l_i,r_i)$表示坐标$(x_i,l_i)$到$(x_i,r_i)$的人在抬头听讲。保证每个人至多在一组里。求有多少认真听讲的人被挡住了。

  $n\le 10^5, \; 1\le x_i,l_i,r_i \le 10^9$

 

分析:

  可以发现,如果一个段是$(x,l,r)$,那么在第$x+1$行,被这个段挡住的部分会变成$(x+1,l+1,r-1)$。于是只需要维护这些段,每次加入一个新的段的时候跟之前加入的段看一下是否可以合并,同时求出这个段有多少是被挡住了的。讲师推荐用set或数据结构维护。

  奇怪的是,笔者用vector维护,每次换行/加段的时候遍历所有段更新,速度非常快,无压力过大数据,但却被$1\le x_i,l_i,r_i\le 10^3$的小数据一直卡$WA$,已经没有修改的头绪……

 

实现(80分):

#include
#include
#include
#include
#include
#include
#include
#define IL inline
#define UI unsigned int
#define RI register int
using namespace std;
typedef long long LL;
const int N=1e5;
const LL inf=(1LL<<62)-1;

    int n;
    
struct Dat{
    LL x,l,r;
}q[N+3];

IL bool operator<(const Dat a,const Dat b){
    if(a.x==b.x)
        return a.l<b.l;
    return a.x<b.x;
}

struct Seg{
    LL l,r;
    Seg(){}
    Seg(LL p1,LL p2):l(p1),r(p2){}
}non=Seg(inf+2,inf+1);

IL bool operator<(const Seg a,const Seg b){
    if(a.l==b.l)
        return a.r<b.r;
    return a.l<b.l;
}
    
IL Seg cut(Seg a,LL x){
    return Seg(a.l+x,a.r-x);
}

IL LL len(Seg a){
    return a.r-a.l+1;
}

IL Seg operator*(Seg a,Seg b){
    return Seg(max(a.l,b.l),min(a.r,b.r));
}

IL Seg operator^(Seg a,Seg b){
    return Seg(min(a.l,b.l),max(a.r,b.r));
}

    LL ans;
    typedef vector arr;
    arr a1,a2,*a,*b;

IL void swap(arr *&x,arr *&y){
    arr *t=x;    x=y;    y=t;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",&q[i].x,&q[i].l,&q[i].r);
    
    sort(q+1,q+n+1);
    a1.clear();    a=&a1;    b=&a2;
    ans=q[0].x=0;
    for(int i=1;i<=n;i++){
        if(q[i].x!=q[i-1].x){
            LL det=q[i].x-q[i-1].x;
            b->clear();
            for(UI j=0;jsize();j++){
                Seg x=cut((*a)[j],det);
                if(len(x)>0)
                    b->push_back(x);
                
            }
            swap(a,b);
            
        }
        
        Seg x=Seg(q[i].l,q[i].r);
        b->clear();
        for(UI j=0;jsize();j++){
            Seg y=(*a)[j];
            LL len0=len(x*y);
            if(len0>0){
                ans+=len0;    x=x^y;
            }
            else 
                b->push_back(y);
            
        }
        b->push_back(x);
        swap(a,b);
        
    }
    
    printf("%lld",ans);

    return 0;

}
View Code

 

小结:

  模拟赛的时候怂成狗,感觉啥也弄不出来,简直不堪回首。复盘一码,捶胸顿足。

你可能感兴趣的