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<ll, ll>, int>> xs;
  set<pair<pair<ll, ll>, 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});
  }
  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<ll, ll>, int>>::iterator> ex;
    vector<set<pair<pair<ll, ll>, int>>::iterator> ey;
    xs.insert({{x[i], y[i]}, i});
    ys.insert({{y[i], x[i]}, i});
    ex.push_back(xs.find({{x[i], y[i]}, i}));
    ey.push_back(ys.find({{y[i], x[i]}, i}));
    if (d[i] == 'U') {
      auto p = xs.find({{x[i], y[i]}, i});
      auto p2 = ys.find({{y[i], x[i]}, i});
      ++p;
      ++p2;
      while (p != xs.end() && (*p).first.first == x[i]) {
	int k = (*p).second;
	if (y[i] < y[k]) {
	  if (at[k] == t) {
	    at[k] = dist(i, k) + tm;
	    if (at[k] > t) at[k] = t;
	    else if (d[k] != d[i]) v.push({-at[k], k});
	  }
	  ex.push_back(p);
	  ey.push_back(p2);
	}
	++p;
	++p2;
      }
    }
    if (d[i] == 'D') {
      auto p = xs.find({{x[i], y[i]}, i});
      auto p2 = ys.find({{y[i], x[i]}, i});
      if (p != xs.begin()) {
	p--;
	p2--;
	while ((*p).first.first == x[i]) {
	  int k = (*p).second;
	  if (y[i] > y[k]) {
	    if (at[k] == t) {
	      at[k] = dist(i, k) + tm;
	      if (at[k] > t) at[k] = t;
	      else if (d[k] != d[i]) v.push({-at[k], k});
	    }
	    ex.push_back(p);
	    ey.push_back(p2);
	  }
	  if (p == xs.begin()) break;
	  --p;
	  --p2;
	}
      }
    }
    if (d[i] == 'R') {
      auto p = ys.find({{y[i], x[i]}, i});
      auto p2 = xs.find({{x[i], y[i]}, i});
      ++p;
      ++p2;
      while (p != ys.end() && (*p).first.first == y[i]) {
	int k = (*p).second;
	if (x[i] < x[k]) {
	  if (at[k] == t) {
	    at[k] = dist(i, k) + tm;
	    if (at[k] > t) at[k] = t;
	    else if (d[k] != d[i]) v.push({-at[k], k});
	  }
	  ey.push_back(p);
	  ex.push_back(p2);
	}
	++p;
	++p2;
      }
    }
    if (d[i] == 'L') {
      auto p = ys.find({{y[i], x[i]}, i});
      auto p2 = xs.find({{x[i], y[i]}, i});
      if (p != ys.begin()) {
	--p;
	--p2;
	while ((*p).first.first == y[i]) {
	  int k = (*p).second;
	  if (x[i] > x[k]) {
	    if (at[k] == t) {
	      at[k] = dist(i, k) + tm;
	      if (at[k] > t) at[k] = t;
	      else if (d[k] != d[i]) v.push({-at[k], k});
	    }
	    ey.push_back(p);
	    ex.push_back(p2);
	  }
	  if (p == ys.begin()) break;
	  --p;
	  --p2;
	}
      }
    }
    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: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffec425a118 ***

Test 4

Verdict: RUNTIME ERROR

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffe3465dd08 ***

Test 8

Verdict: ACCEPTED

Test 9

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffea54fedb8 ***

Test 10

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffdafd00748 ***

Test 11

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffeaeaa5bb8 ***

Test 12

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffd76076678 ***

Test 13

Verdict: ACCEPTED

Test 14

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffe5d4820a8 ***

Test 15

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffcfd7d79d8 ***

Test 16

Verdict: ACCEPTED

Test 17

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffd8c6b3f28 ***

Test 18

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007ffe586dc618 ***

Test 19

Verdict: RUNTIME ERROR

Test 20

Verdict: RUNTIME ERROR

*** Error in `input/code': free(): invalid pointer: 0x00007fff284f91d8 ***

Test 21

Verdict: RUNTIME ERROR

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