D题感觉是random数据

暴力写法 1500ms

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x;
	int y;
};
bool cmp1(node a,node b){
	return a.x<b.x;
}
bool cmp2(node a,node b){
	return a.x>b.x;
}
bool cmp3(node a,node b){
	return a.y<b.y;
}
bool cmp4(node a,node b){
	return a.y>b.y;
}
unordered_map<long long,vector<long long>>mp1;
unordered_map<long long,vector<long long>>mp2;
unordered_map<long long,map<long long,int>>f;
unordered_map<long long,map<long long,int>>mp;
node a[200010];
int main(){
	int n,m;
	cin>>n>>m;
	int sx,sy;
	cin>>sx>>sy;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		f[a[i].x][a[i].y]=1;
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;i++){
		mp1[a[i].y].push_back(a[i].x);
	}
	sort(a+1,a+n+1,cmp3);
	for(int i=1;i<=n;i++){
		mp2[a[i].x].push_back(a[i].y); 
	}
	long long X=sx;
	long long Y=sy; 
	int cnt=0;
	while(m--){
		string p;
		cin>>p;
		long long c;
		cin>>c;
		if(p=="U"){
			int l=lower_bound(mp2[X].begin(),mp2[X].end(),Y)-mp2[X].begin();
			int r=upper_bound(mp2[X].begin(),mp2[X].end(),Y+c)-mp2[X].begin();
			for(int i=l;i<=r-1;i++){
				//cout<<X<<" "<<mp2[X][i]<<endl;
				if(!mp[X][mp2[X][i]]){
					mp[X][mp2[X][i]]=1;
					cnt++;
				}
			}
			Y+=c;
		}
		else if(p=="D"){
			int l=lower_bound(mp2[X].begin(),mp2[X].end(),Y-c)-mp2[X].begin();
			int r=upper_bound(mp2[X].begin(),mp2[X].end(),Y)-mp2[X].begin();
			//cout<<l<<" "<<r<<endl;
			for(int i=l;i<=r-1;i++){
				if(!mp[X][mp2[X][i]]){
					mp[X][mp2[X][i]]=1;
					cnt++;
				}
			}
			Y-=c;
		}
		else if(p=="L"){
			int l=lower_bound(mp1[Y].begin(),mp1[Y].end(),X-c)-mp1[Y].begin();
			int r=upper_bound(mp1[Y].begin(),mp1[Y].end(),X)-mp1[Y].begin();
			for(int i=l;i<=r-1;i++){
				//cout<<mp1[Y][i]<<" "<<Y<<endl;
				if(!mp[mp1[Y][i]][Y]){
					mp[mp1[Y][i]][Y]=1;
					cnt++;
				}
			}
			X-=c;
		}
		else if(p=="R"){
			int l=lower_bound(mp1[Y].begin(),mp1[Y].end(),X)-mp1[Y].begin();
			int r=upper_bound(mp1[Y].begin(),mp1[Y].end(),X+c)-mp1[Y].begin();
			for(int i=l;i<=r-1;i++){
				//cout<<mp1[Y][i]<<" "<<Y<<endl;
				if(!mp[mp1[Y][i]][Y]){
					mp[mp1[Y][i]][Y]=1;
					cnt++;
				}
			}
			X+=c;
		}
	}
	cout<<X<<" "<<Y<<" "<<cnt<<endl;
  return 0;
}