Robots

#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define LINF 999999999999999999LL
#define N (1<<17)
#define M 1000000007

using namespace std;

ll x[100001];
ll y[100001];
char d[100001];
ll at[100001];

ll dist (int a, int b) {
  return abs(x[a] - x[b]) + abs(y[a] - y[b]);
}

int main () {
  set<pair<pair<int, int>, int>> xs;
  set<pair<pair<int, int>, int>> ys;
  int n;
  ll t;
  cin>>n>>t;
  for (int i = 1; i <= n; i++) {
    cin>>x[i]>>y[i]>>d[i];
    at[i] = t;
    if (i > 1) xs.insert({{x[i], y[i]}, i});
    if (i > 1) ys.insert({{y[i], x[i]}, i});
  }
  dist(2, 5);
  at[1] = 0;
  priority_queue<pair<ll, int>> v;
  v.push({0, 1});
  
  while (!v.empty()) {
    if (xs.size() == 0) break;
    int i = v.top().second;
    ll tm = -v.top().first;
    v.pop();
    vector<set<pair<pair<int, int>, int>>::iterator> ex;
    vector<set<pair<pair<int, int>, int>>::iterator> ey;
    if (d[i] == 'U') {
      auto p = xs.lower_bound({{x[i], y[i]}, 0});
      while (p != xs.end() && (*p).first.first == x[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ex.push_back(p);
	++p;
      }
    }
    if (d[i] == 'D') {
      auto p = xs.upper_bound({{x[i], y[i]}, 0});
      p--;
      while (p != (--xs.begin()) && (*p).first.first == x[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ex.push_back(p);
	--p;
      }
    }
    if (d[i] == 'R') {
      auto p = ys.lower_bound({{y[i], x[i]}, 0});
      while (p != ys.end() && (*p).first.first == y[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ey.push_back(p);
	++p;
      }
    }
    if (d[i] == 'L') {
      auto p = ys.upper_bound({{y[i], x[i]}, 0});
      p--;
      while (p != (--ys.begin()) && (*p).first.first == y[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ey.push_back(p);
	--p;
      }
    }
    for (auto a : ex) xs.erase(a);
    for (auto a : ey) ys.erase(a);
  }
  
  for (int i = 1; i <= n; i++) {
    if (d[i] == 'U') cout<<x[i]<<" "<<y[i] + t - at[i]<<endl;
    if (d[i] == 'D') cout<<x[i]<<" "<<y[i] - t + at[i]<<endl;
    if (d[i] == 'L') cout<<x[i] - t + at[i]<<" "<<y[i]<<endl;
    if (d[i] == 'R') cout<<x[i] + t - at[i]<<" "<<y[i]<<endl;
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: RUNTIME ERROR

Test 12

Verdict: RUNTIME ERROR

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: RUNTIME ERROR

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED