Robots

input/code.cpp: In function 'int main()':
input/code.cpp:52:21: warning: array subscript has type 'char' [-Wchar-subscripts]
     d[i] = trans[fak];
                     ^
input/code.cpp:80:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j+bi < rip[0][x[i]].size() && rip[0][x[i]][j+bi] < y[i])
                                 ^
input/code.cpp:89:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j+bi < rip[2][x[i]].size() && rip[2][x[i]][j+bi] <= y[i])
                                 ^
input/code.cpp:94:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j < rip[2][x[i]].size())
                                ^
input/code.cpp:100:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j+bi < rip[1][y[i]].size() && rip[1][y[i]][j+bi] < x[i])
                                 ^
input/code.cpp:109:33: warnin...

#include <bits/stdc++.h>

#define i64 long long
#define u64 unsigned long long
#define i32 int
#define u32 unsigned int

#define pii pair<int, int>
#define pll pair<long long, long long>

#define ld long double
#define defmod 1000000007

#define mati64(a,b) vector<vector<i64>>(a, vector<i64>(b, 0));
#define sit set<i64>::iterator
using namespace std;
i64 n, t; 
int d[101010];
i64 x[101010], y[101010];
int trans[1010];
int fuckme[10][2];
map<i64, vector<i64>> rip[4];
vector<int> v[101010];
vector<int> v2[101010];
map<pair<pair<i64, i64>, int>, int> id;

i64 manh(int i, int j){
  return abs(x[i]-x[j])+abs(y[i]-y[j]);
}
int main(){
  //set<int> kk;
  //kk.insert(0);
  //cout <<"wtf"<< *(--kk.lower_bound(1)) << endl;
  trans['U'] = 0;
  trans['D'] = 2;
  trans['R'] = 1;
  trans['L'] = 3;
  fuckme[0][0] = 0;
  fuckme[0][1] = 1;
  fuckme[1][0] = 1;
  fuckme[1][1] = 0;
  fuckme[2][0] = 0;
  fuckme[2][1] = -1;
  fuckme[3][0] = -1;
  fuckme[3][1] = 0;
  cin.sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> t;
  for(int i = 0; i < n; ++i){
    char fak;
    cin >> x[i] >> y[i] >> fak;
    d[i] = trans[fak];
    id[{{x[i], y[i]}, d[i]}] = i;
    if(d[i] == 0 || d[i] == 2){
      //cout << "dir " << d[i] << " x " << x[i] << " y " << y[i] << endl; 
      rip[d[i]][x[i]].push_back(y[i]);
    }
    else{
      //cout << "dir " << d[i] << " y " << y[i] << " x " << x[i] << endl; 
      rip[d[i]][y[i]].push_back(x[i]);
    }
  }
  for(auto&f: rip[0]){
    sort(f.second.begin(), f.second.end());
  }
  for(auto&f: rip[1]){
    sort(f.second.begin(), f.second.end());
  }
  for(auto&f: rip[2]){
    sort(f.second.begin(), f.second.end());
  }
  for(auto&f: rip[3]){
    sort(f.second.begin(), f.second.end());
  }
  for(int i = 0; i < n; ++i){
    
    if(rip[0][x[i]].size()){
      int j = -1;
      for(int bi = 1<<17; bi > 0; bi/=2){
	while(j+bi < rip[0][x[i]].size() && rip[0][x[i]][j+bi] < y[i])
	  j+=bi;
      }
      if(j >= 0)
	v[i].push_back(id[{{x[i], rip[0][x[i]][j]}, 0}]);
    }
    if(rip[2][x[i]].size()){
      int j = -1;
      for(int bi = 1<<17; bi > 0; bi/=2){
	while(j+bi < rip[2][x[i]].size() && rip[2][x[i]][j+bi] <= y[i])
	  j+=bi;
      }
      j++;
      
      if(j < rip[2][x[i]].size())
	v[i].push_back(id[{{x[i], rip[2][x[i]][j]}, 2}]);
    }
    if(rip[1][y[i]].size()){
      int j = -1;
      for(int bi = 1<<17; bi > 0; bi/=2){
	while(j+bi < rip[1][y[i]].size() && rip[1][y[i]][j+bi] < x[i])
	  j+=bi;
      }
      if(j >= 0)
	v[i].push_back(id[{{rip[1][y[i]][j], y[i]}, 1}]);
    }
    if(rip[3][y[i]].size()){
     int j = -1;
      for(int bi = 1<<17; bi > 0; bi/=2){
	while(j+bi < rip[3][y[i]].size() && rip[3][y[i]][j+bi] <= x[i])
	  j+=bi;
      }
      j++;
      
      if(j < rip[3][y[i]].size())
	v[i].push_back(id[{{rip[3][y[i]][j], y[i]}, 3}]);
    }
    //cout << i << " paas ";
    //for(auto f: v[i])
    //  cout << f<< " ";
    //cout << endl;
  }
  for(int i = 0; i < n; ++i){
    for(auto f: v[i])
      v2[f].push_back(i);
    
  }
  priority_queue<pair<i64, int>> q;
  q.push({0, 0});
  pair<i64, i64> ans[101010];
  bool d1[101010] = {0};
  while(!q.empty()){
    int cur = q.top().second;
    i64 dis = -q.top().first;
    q.pop();
    if(d1[cur])
      continue;
    d1[cur] = 1;
    if(dis > t){
      ans[cur] = {x[cur], y[cur]};
    }
    else{
      ans[cur] = {x[cur]+fuckme[d[cur]][0]*(t-dis), y[cur]+fuckme[d[cur]][1]*(t-dis)};
    }
    for(auto f: v2[cur])
      q.push({-(dis+manh(cur, f)), f});
  }
  for(int i = 0; i < n; ++i){
    if(!d1[i])
      cout << x[i] << " " << y[i] << endl;
    else
      cout << ans[i].first << " " << ans[i].second << endl;
  }
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

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