Submission #406811

---

Source Code Expand

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;



typedef pair<int, int> P;

vector<set<int>> unX(400010);
vector<set<int>> unY(400010);
vector<set<int>> runX(400010);
vector<set<int>> runY(400010);

set<P> used;

const int pivot = 200005;

inline void ins(int x, int y){
	if (used.count(make_pair(y, x)))return;
	unX[pivot + x].insert(pivot + y);
	unY[pivot + y].insert(pivot + x);
	runX[pivot + x].insert(-(pivot + y));
	runY[pivot + y].insert(-(pivot + x));
	//printf("%d,%d\n", x, y);
}

inline void era(int x, int y){
	if (used.count(make_pair(y, x))==0)return;
	unX[pivot + x].erase(pivot + y);
	unY[pivot + y].erase(pivot + x);
	runX[pivot + x].erase(-(pivot + y));
	runY[pivot + y].erase(-(pivot + x));
}
int main(void){
	int K;
	char c;
	string s;
	int x = 0;
	int y = 0;
	cin >> K>>s;
	ins(0, 1);
	ins(1, 0);
	ins(-1, 0);
	ins(0, -1);

	used.insert(make_pair(x, y));
	for (int i = 0; i < K; i++){
		c = s[i];
		switch (c)
		{
		case 'U':
			y=*unY[pivot + x].lower_bound(pivot + y);
			y -= pivot;
			used.insert(make_pair(x, y));
			break;
		case 'D':
			y = -*runY[pivot + x].lower_bound(-(pivot + y));
			y -= pivot;

			used.insert(make_pair(x, y));
			break;
		case 'L':
			x = -*runX[pivot + y].lower_bound(-(pivot + x));
			x -= pivot;
			used.insert(make_pair(x, y));
			break;
		case 'R':
			x = *unX[pivot + y].lower_bound(pivot + x);
			x -= pivot;
			used.insert(make_pair(x, y));
			break;
		default:
			break;
		}
		era(y, x);
		ins(y, x+1);
		ins(y+1, x);
		ins(y-1, x);
		ins(y, x-1);
	//	cout << x << y << endl;
	}

	cout << x <<" "<< y << endl;
	return(0);
}

Submission Info

Judge Result