Submission #314436

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue> 
#define MX 100005
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int X[MX], Y[MX], ny, nx, N;
pii p[MX];
char dir[MX];
LL mark[MX], T;
set <pii> xset[MX], yset[MX];
set <pii> :: iterator  it, it1;
struct Data {
	int u;
	LL t;
	Data(int u = 0, LL t = 0) : u(u), t(t) {}
	
	bool operator <(const Data &b) const {
		return t > b.t;
	}
}D;

int getX(int x) {return lower_bound(X, X + nx, x) - X;}
int getY(int y) {return lower_bound(Y, Y + ny, y) - Y;}
priority_queue <Data> Q;
int main() {
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	
	scanf("%d%lld", &N, &T);
	int i, x, y;
	LL k, rx, ry;
	for (i = 0; i < N; i++) {
		scanf("%d%d", &p[i].first, &p[i].second);
		X[i] = p[i].first, Y[i] = p[i].second;
		scanf("%1s", dir + i);
	}
	sort(X, X + N);
	sort(Y, Y + N);
	nx = unique(X, X + N) - X;
	ny = unique(Y, Y + N) - Y;
	for (i = 0; i < N; i++) {
		x = getX(p[i].first);
		xset[x].insert(pii(p[i].second, i));
		y = getY(p[i].second);
		yset[y].insert(pii(p[i].first, i));
	}
	memset(mark, -1, sizeof mark);
	mark[0] = 0;
	x = getX(p[0].first);
	xset[x].erase(pii(p[0].second, 0));
	y = getY(p[0].second);
	yset[y].erase(pii(p[0].first, 0));
	Q.push(Data(0, 0));
	while (!Q.empty()) {
		D = Q.top();
		Q.pop();
		k = D.u;
		x = p[k].first, y = p[k].second;
		if (dir[k] == 'U') {
			x = getX(x);
			it = xset[x].lower_bound(pii(y, 0));
			it1 = it;
			for (; it != xset[x].end(); it++) {
				mark[it -> second] = D.t + it -> first - y;
				Q.push(Data(it -> second, mark[it -> second]));
				int z = getY(it -> first);
				yset[z].erase(pii(p[k].first, it -> second));
			}
			xset[x].erase(it1, xset[x].end());
		} else if (dir[k] == 'R') {
			y = getY(y);
			it = yset[y].lower_bound(pii(x, 0));
			it1 = it;
			for (; it != yset[y].end(); it++) {
				mark[it -> second] = D.t + it -> first - x;
				Q.push(Data(it -> second, mark[it -> second]));
				int z = getX(it -> first);
				xset[z].erase(pii(p[k].second, it -> second));
			}
			yset[y].erase(it1, yset[y].end());
		} else if (dir[k] == 'D') {
			x = getX(x);
			it1 = xset[x].lower_bound(pii(y, 0));
			for (it = xset[x].begin(); it != it1; it++) {
				mark[it -> second] = D.t + y - it -> first;
				Q.push(Data(it -> second, mark[it -> second]));
				int z = getY(it -> first);
				yset[z].erase(pii(p[k].first, it -> second));
			}
			xset[x].erase(xset[x].begin(), it1);
		} else if (dir[k] == 'L') {
			y = getY(y);
			it1 = yset[y].lower_bound(pii(x, 0));
			for (it = yset[y].begin(); it != it1; it++) {
				mark[it -> second] = D.t + x - it -> first;
				Q.push(Data(it -> second, mark[it -> second]));
				int z = getX(it -> first);
				xset[z].erase(pii(p[k].second, it -> second));
			}
			yset[y].erase(yset[y].begin(), it1);
		}
	}
	for (i = 0; i < N; i++) {
		if (mark[i] == -1 || mark[i] >= T) k = 0;
		else k = T - mark[i];
		rx = p[i].first, ry = p[i].second;
		if (dir[i] == 'U') ry += k;
		else if (dir[i] == 'D') ry -= k;
		else if (dir[i] == 'L') rx -= k;
		else if (dir[i] == 'R') rx += k;
		printf("%lld %lld\n", rx, ry);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:38:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:40:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result