38分求调,5,6两个包只过了前两个点
查看原帖
38分求调,5,6两个包只过了前两个点
757101
junee楼主2024/5/25 16:32
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int N=2e5+10;
typedef long long LL;
int n;
LL ans=0;
vector<LL>v;
struct node{
	LL l,r,cnt,len;
}tr[N*4];
struct edge{
	LL x,y1,y2,k;
}e[N];
bool cmp(edge a,edge b){
	return a.x<b.x;
}
int find(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin();
}
void pushup(int u){
	if(tr[u].cnt)tr[u].len=v[tr[u].r+1]-v[tr[u].l];
    else if(tr[u].l!=tr[u].r)tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    else tr[u].len=0;
}
void build(int u,int l,int r){
	tr[u]={l,r,0,0};
	if(l==r)return;
	int mid=(l+r)>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r); 
}
void modify(int u,int l,int r,int k){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].cnt+=k;
		pushup(u);
		return;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	if(l<=mid)modify(u<<1,l,r,k);
	if(r>mid)modify(u<<1|1,l,r,k);
	pushup(u);
}
int xx1,xx2,yy1,yy2,T,j=0;
char a;
int main(){
	cin>>n>>T;
	xx1=yy1=0,xx2=yy2=n;
	for(LL i=0,x1,x2,y1,y2,d;i<T;i++){
		cin>>a>>d;
		if(a=='W')x1=xx1-d,y1=yy1,x2=xx2,y2=yy2,xx1-=d,xx2-=d;
		if(a=='E')x1=xx1,y1=yy1,x2=xx2+d,y2=yy2,xx1+=d,xx2+=d;
		if(a=='N')x1=xx1,y1=yy1,x2=xx2,y2=yy2+d,yy1+=d,yy2+=d;
		if(a=='S')x1=xx1,y1=yy1-d,x2=xx2,y2=yy2,yy1-=d,yy2-=d;
		e[j++]={x1,y1,y2,1};
		e[j++]={x2,y1,y2,-1};
		v.push_back(y1),v.push_back(y2);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	build(1,0,v.size()-2);
	sort(e,e+j,cmp);
	for(int i=0;i<j;i++){
	    if(i)ans+=tr[1].len*(e[i].x-e[i-1].x);
		modify(1,find(e[i].y1),find(e[i].y2)-1,e[i].k);
	}
	cout<<ans;
	return 0;
}
2024/5/25 16:32
加载中...