求条
查看原帖
求条
1243587
shiyilang0910楼主2024/12/23 21:25
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int n,m,sx,sy;
struct node{
	int x,y;
	bool vis;
}a[200005];
int r[200005],l[200005];
char d[200005];
int c[200005];
bool cmp(node x,node y){
	if (x.x!=y.x){
		return x.x<y.x;
	}
	return x.y<y.y;
}
signed main(){
	cin>>n>>m;
	cin>>sx>>sy;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		r[i]=a[i].x;
		l[i]=a[i].y;
	}
	int xx,yy,sum=0;
	for(int i=1;i<=m;i++){
		cin>>d[i]>>c[i];
		xx=sx;
		yy=sy;
		if (d[i]=='U'){
			sy+=c[i];
		}
		if (d[i]=='D'){
			sy-=c[i];
		}
		if (d[i]=='L'){
			sx-=c[i];
		}
		if (d[i]=='R'){
			sx+=c[i];
		}
		if (d[i]=='D'||d[i]=='U'){
			int h1=lower_bound(r+1,r+1+n,sx)-r;
			int h2=upper_bound(r+1,r+1+n,sx)-r-1;
			if (h1>h2||h1>n){
				continue;
			}
			int j1=lower_bound(r+h1,r+1+h2,min(sy,yy))-r;
			int j2=upper_bound(r+h1,r+1+h2,max(sy,yy))-r-1;
			if (j1>j2||j1>n){
				continue;
			}
			for(int j=max(j1,1*1LL);j<=min(j2,n);j++){
				if (!a[j].vis){
					sum++;
					a[j].vis=1;
				}
			}
		}else{
			int h1=lower_bound(r+1,r+1+n,sy)-r;
			int h2=upper_bound(r+1,r+1+n,sy)-r-1;
			if (h1>h2||h1>n){
				continue;
			}
			int j1=lower_bound(r+h1,r+1+h2,min(sx,xx))-r;
			int j2=upper_bound(r+h1,r+1+h2,max(sx,xx))-r-1;
			if (j1>j2||j1>n){
				continue;
			}
			for(int j=max(j1,1*1LL);j<=min(j2,n);j++){
				if (!a[j].vis){
					sum++;
					a[j].vis=1;
				}
			}
		}
	}
	cout<<sx<<" "<<sy<<" "<<sum;
	return 0;
}
2024/12/23 21:25
加载中...