38pts求调
查看原帖
38pts求调
549309
imfbust楼主2024/9/15 13:48
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
long long n,k,x[N];
long long ans;
struct Node{
    long long l,r,h;
    int mark;
    bool operator<(const Node&x) const{
        return h<x.h;
    }
}line[N];
struct Tree{
    long long l,r,sum;
    long long len;
}tree[N];
void build(long long p,long long l,long long r){
    tree[p].l=l;
    tree[p].r=r;
    tree[p].len=0;
    tree[p].sum=0;
    if(l==r) return ;
    long long mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    return;
}
void pushup(long long p){
    if(tree[p].sum) tree[p].len=x[tree[p].r+1]-x[tree[p].l];
    else tree[p].len=tree[p*2].len+tree[p*2+1].len;
}
void update(long long p,long long l,long long r,int c){
    if(x[tree[p].r+1]<=l||r<=x[tree[p].l]) return ;
    if(l<=x[tree[p].l]&&x[tree[p].r+1]<=r){
        tree[p].sum+=c;
        pushup(p);
        return ;
    }
    update(p*2,l,r,c);
    update(p*2+1,l,r,c);
    pushup(p);
}
int main(){
    freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
    scanf("%lld%lld",&k,&n);
    char s;
    int a,b=0,c=0;
    n+=1;
    x[1]=0;
    x[2]=k;
    line[1]=(Node){0,k,0,1};
    line[2]=(Node){0,k,k,-1};
    for(int i=2;i<=n;i++){
        scanf("%s%d",&s,&a);
        if(s=='N'){
            x[i*2-1]=b;
            x[i*2]=b+k;
            line[i*2-1]=(Node){b,b+k,c,1};
            line[i*2]=(Node){b,b+k,c+a+k,-1};
            c+=a;
        }
        else if(s=='E'){
            x[i*2-1]=b;
            x[i*2]=b+k+a;
            line[i*2-1]=(Node){b,b+k+a,c,1};
            line[i*2]=(Node){b,b+k+a,c+k,-1};
            b+=a;
        }
        else if(s=='W'){
            x[i*2-1]=b-a;
            x[i*2]=b+k;
            line[i*2-1]=(Node){b-a,b+k,c,1};
            line[i*2]=(Node){b-a,b+k,c+k,-1};
            b-=a;
        }
        else{
            x[i*2-1]=b;
            x[i*2]=b+k;
            line[i*2-1]=(Node){b,b+k,c-a,1};
            line[i*2]=(Node){b,b+k,c+k,-1};
            c-=a;
        }
    }
    n<<=1;
    sort(line+1,line+n+1);
    sort(x+1,x+n+1);
    long long tot=unique(x+1,x+n+1)-x-1;
    build(1,1,tot-1);
    for(int i=1;i<n;i++){
        update(1,line[i].l,line[i].r,line[i].mark);
        ans+=tree[1].len*(line[i+1].h-line[i].h);
    }
    printf("%lld",ans);
    return 0;
}

2024/9/15 13:48
加载中...