【ACGO巅峰赛#19】T3机器人

与T2相比稍复杂的模拟题。

首先此题很显然是模拟每次的走动，但是暴力检查柱子会TLE。我们首先注意到如果当前 $x/y$ 方向没有柱子，那么这个方向的移动不会受到任何影响。这启示我们使用 $x,y$ 方向上的两个map来记录柱子所在的行或列。

如果当前移动的方向有柱子，那我们可以把这个方向上的柱子全部提取出来。（这里可以用之前记录的map为有柱子的所有方向都创建一个序列）不难发现，如果是向 $x/y$ 增加的方向移动，那么最远移动距离就是 $x/y$ 的后继 $-1$。若反方向移动，则最远移动距离就是 $x/y$ 的前驱 $+1$。

（名词解释）设指定数为 $a$，则：

·后继：一个序列中大于 $a$ 的最小值。

·前驱：一个序列中小于 $a$ 的最大值。

若将要移动的位置比最远移动距离要远，那么机器人只能停在最远移动距离处。否则正常移动。

而求序列中指定数前驱或后继可以用平衡树，但是在不涉及排名的情况下，使用stl容器set更为简便。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+10;
int n,m,a[N];
map<int,int> xm,ym;
int idx,idy;
set<int> sx[N],sy[N];

signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	int tx,ty;
	int q1,q2;
	for(int i=1;i<=n;i++){
		cin>>q1>>q2;
		if(!xm[q1]){
			tx = xm[q1] = ++idx;
		}
		else{
			tx = xm[q1];
		}
		if(!ym[q2]){
			ty = ym[q2] = ++idy;
		}
		else{
			ty = ym[q2];
		}
		sx[tx].insert(q2);
		sy[ty].insert(q1);
	}
	char op;
	int x=0,y=0;
	for(int i=1;i<=m;i++){
		cin>>op>>q1;
		if(op=='w'){
			int cx = xm[x];
			if(!cx){
				y += q1;
				continue;
			}
			if(y>*sx[cx].rbegin()){
				y += q1;
				continue;
			}
			int tmp = *sx[cx].upper_bound(y)-1;
			if(tmp>y+q1) y += q1;
			else y = tmp;
		}
		else if(op=='d'){
			int cx = xm[x];
			if(!cx){
				y -= q1;
				continue;
			}
			if(y<*sx[cx].begin()){
				y -= q1;
				continue;
			}
			auto it = sx[cx].lower_bound(y);
			it--;
			int tmp = *it+1;
			if(tmp<y-q1) y -= q1;
			else y = tmp;	
		}
		else if(op=='r'){
			int cy = ym[y];
			if(!cy){
				x += q1;
				continue;
			}
			if(x>*sy[cy].rbegin()){
				x += q1;
				continue;
			}
			int tmp = *sy[cy].upper_bound(x)-1;
			if(tmp>x+q1) x += q1;
			else x = tmp;
		}
		else if(op=='l'){
			int cy = ym[y];
			if(!cy){
				x -= q1;
				continue;
			}
			if(x<*sy[cy].begin()){
				x -= q1;
				continue;
			}
			auto it = sy[cy].lower_bound(x);
			it--;
			int tmp = *it+1;
			if(tmp<x-q1) x -= q1;
			else x = tmp;
		}
	}
	cout<<x<<' '<<y<<endl;
	
	return 0;
}