扫描线 MLE 38pts 求调教
查看原帖
扫描线 MLE 38pts 求调教
423520
wizard(偷开O2楼主2024/7/12 17:01
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls lson[now]
#define rs rson[now]
#define mid ((l+r)>>1)
#define mod 998244353
const int maxn=1e5+10;
int lson[maxn<<2],rson[maxn<<2];
int sum[maxn<<4];
int dex[maxn<<4];
void pushup(int now,int l,int r){
	if(sum[now]){
		dex[now]=r-l+1;
	}else{
		dex[now]=dex[ls]+dex[rs];
	}
	return ;
}
int tot=1;
void modify(int &now,int l,int r,int L,int R,int f){
	if(!now){
		now=++tot;
	}
	if(L<=l&&r<=R){
		sum[now]+=f;
		pushup(now,l,r);
		return;
	}
	if(L<=mid){
		modify(ls,l,mid,L,R,f);
	}
	if(mid+1<=R){
		modify(rs,mid+1,r,L,R,f);
	}
	pushup(now,l,r);
	return ;
}
int n;
struct node{
	int t,l,r,f;//横轴 纵l,r 标记 
}a[maxn<<4];
bool cmp(node a,node b){
	return a.t<b.t;
}
int root=1;
int k,x,y;
void init(){
	cin >>k>> n; 
	for(int i=1;i<=n;i++){
		char op;
		int d;
		cin >> op >> d;
		if(op=='N'){
			a[i].f=1,a[i].t=x,a[i].l=y,a[i].r=y+k+d;
			a[i+n].f=-1,a[i+n].t=x+k,a[i+n].l=y,a[i+n].r=y+k+d;
			y+=d;
		}else if(op=='S'){
			a[i].f=1,a[i].t=x,a[i].l=y-d,a[i].r=y+k;
			a[i+n].f=-1,a[i+n].t=x+k,a[i+n].l=y-d,a[i+n].r=y+k;
			y-=d;
		}else if(op=='W'){
			a[i].f=1,a[i].t=x-d,a[i].l=y,a[i].r=y+k;
			a[i+n].f=-1,a[i+n].t=x+k,a[i+n].l=y,a[i+n].r=y+k;
			x-=d;
		}else if(op=='E'){
			a[i].f=1,a[i].t=x,a[i].l=y,a[i].r=y+k;
			a[i+n].f=-1,a[i+n].t=x+k+d,a[i+n].l=y,a[i+n].r=y+k;
			x+=d;
		}
	}
	sort(a+1,a+n+n+1,cmp);
}
void check(){
	int ans=0;
	int pre=0;
	for(int i=1;i<=n*2;i++){//一共2n条边 
		ans+=dex[root]*(a[i].t-pre);
		pre=a[i].t;
		modify(root,-1e9-10,1e9+10,a[i].l,a[i].r-1,a[i].f);
	}
	cout << ans << endl;
	return ;
}
signed main(){
	init();
	check();
	return 0;
}

record

2024/7/12 17:01
加载中...