Robots

input/code.cpp: In function 'int main()':
input/code.cpp:41:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < cmp.size(); ++i) {
                                ^

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll MN = 3e5+100;
ll start[MN];
ll arr[MN];
ll arr2[MN][4];
pair<ll, ll> t[MN];
pair<ll, ll> pck[MN];
set<pair<ll, ll> > sv[MN];
set<pair<ll, ll> > sh[MN];
char dir[MN];
ll mov[MN][2];
ll ans[MN][2];

map<pair<ll, ll>, int> qwe;
int main() {
    ll n,T;
    cin>>n>>T;
    vector<ll> cmp;
    for(ll i = 0; i < n; ++i) {
	cin>>t[i].F>>t[i].S>>dir[i];
	if(dir[i] == 'U') mov[i][1] = 1;
	if(dir[i] == 'D') mov[i][1] = -1;
	if(dir[i] == 'L') mov[i][0] = -1;
	if(dir[i] == 'R') mov[i][0] = 1;
	cmp.push_back(t[i].F);
	cmp.push_back(t[i].S);
	qwe[{t[i].F, t[i].S}] = i;
	ans[i][0] = t[i].F;
	ans[i][1] = t[i].S;
	start[i] = -1;
	arr[i] = -1;
	for(int j = 0; j < 4; ++j) arr2[i][j] = 2e18;
    }
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    map<ll, ll> mp;
    for(ll i = 0; i < cmp.size(); ++i) {
	mp[cmp[i]] = i;
    }
    for(ll i = 0; i < n; ++i) {
	sv[mp[t[i].F]].insert({mp[t[i].S], i});
	sh[mp[t[i].S]].insert({mp[t[i].F], i});
    }
    set<pair<ll, ll> > qq;
    qq.insert({0, 0});
    start[0] = 0;
    ans[0][0] = t[0].F;
    ans[0][1] = t[0].S;
    ans[0][0] += T * mov[0][0];
    ans[0][1] += T * mov[0][1];
    ll cx = mp[t[0].F];
    ll cy = mp[t[0].S];
    sv[cx].erase({t[0].S, 0});
    sh[cy].erase({t[0].F, 0});
    while(qq.size()) {
	auto p = *qq.begin();
	qq.erase(*qq.begin());
	ll x = t[p.S].F + mov[p.S][0] * (p.F-start[p.S]);
	ll y = t[p.S].S + mov[p.S][1] * (p.F-start[p.S]);
	int c = qwe[{x, y}];
	if(p.F > T) break;
	if(start[c] == -1) {
	    ans[c][0] = t[c].F;
	    ans[c][1] = t[c].S;
	    ans[c][0] += (T-p.F)*mov[c][0];
	    ans[c][1] += (T-p.F)*mov[c][1];

	    start[c] = p.F;
	    qq.insert({p.F, c});
	    ll cx = mp[t[c].F];
	    ll cy = mp[t[c].S];
	    sv[cx].erase({t[c].S, c});
	    sh[cy].erase({t[c].F, c});
	}
	//ll px = mp[x];
	//ll py = mp[y];
	if(dir[p.S] == 'U' && mp.count(x)) {
	    ll px = mp[x];

	    auto z = sv[px].lower_bound({y, 0});
	    if(z == sv[px].end()) continue;
	    auto z2 = *z;
	    ll time = t[z2.S].S-y + p.F;
	    //cout<<"LOL "<<time<<'\n';
	    if(arr2[z2.S][2] <= time) {
		continue;
	    }
	    arr2[z2.S][2] = time;
	    qq.insert({time, p.S});
	}
	if(dir[p.S] == 'D' && mp.count(x)) {
	    ll px = mp[x];
	    auto z = sv[px].lower_bound({y, 0});
	    if(z == sv[px].begin()) continue;
	    --z;
	    auto z2 = *z;
	    ll time = y-t[z2.S].S + p.F;
	    if(arr2[z2.S][0] <= time) {
		continue;
	    }
	    arr2[z2.S][0] = time;
	    qq.insert({time, p.S});
	}
	if(mp.count(y)) {
	    ll py = mp[y];
	    if(dir[p.S] == 'R') {
		auto z = sh[py].lower_bound({x, 0});
		if(z == sh[py].end()) continue;
		auto z2 = *z;
		ll time = t[z2.S].F-x + p.F;
		if(arr2[z2.S][3] <= time) {
		    continue;
		}
		arr2[z2.S][3] = time;
		qq.insert({time, p.S});
	    }
	    if(dir[p.S] == 'L') {
		auto z = sh[py].lower_bound({x, 0});
		if(z == sh[py].begin()) continue;
		--z;
		auto z2 = *z;
		ll time = x - t[z2.S].F + p.F;
		if(arr2[z2.S][1] <= time) {
		    continue;
		}
		arr2[z2.S][1] = time;
		qq.insert({time, p.S});
	    }
	}
    }
    for(int i = 0; i < n; ++i) {
	cout<<ans[i][0]<<' '<<ans[i][1]<<'\n';
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: ACCEPTED

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER