Submission #4318244

---

Source Code Expand

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

int INF = 1 << 29;

void main() {
    auto N = readln.chomp.to!int;
    auto S = readln.chomp;

    int x = N;
    int y = N;

    alias RBT = RedBlackTree!(Tuple!(int, int));
    auto row = new RBT[](2*N+10);
    auto col = new RBT[](2*N+10);
    foreach (i; 0..2*N+10) row[i] = new RBT(tuple(-INF, -INF), tuple(INF, INF));
    foreach (i; 0..2*N+10) col[i] = new RBT(tuple(-INF, -INF), tuple(INF, INF));
    row[x].insert(tuple(y, y));
    col[y].insert(tuple(x, x));

    Tuple!(int, int) xrange = tuple(x, x);
    Tuple!(int, int) yrange = tuple(y, y);

    void insert(int x, int y) {
        auto ncol = tuple(x, x);
        auto nrow = tuple(y, y);

        auto left = col[y].lowerBound(tuple(x, x)).back;
        auto right = col[y].upperBound(tuple(x, x)).front;
        auto up = row[x].lowerBound(tuple(y, y)).back;
        auto down = row[x].upperBound(tuple(y, y)).front;

        if (left[1] + 1 == x) {
            col[y].removeKey(left);
            ncol[0] = left[0];
        }
        if (right[0] - 1 == x) {
            col[y].removeKey(right);
            ncol[1] = right[1];
        }
        if (up[1] + 1 == y) {
            row[x].removeKey(up);
            nrow[0] = up[0];
        }
        if (down[0] - 1 == y) {
            row[x].removeKey(down);
            nrow[1] = down[1];
        }

        col[y].insert(ncol);
        row[x].insert(nrow);

        xrange = ncol;
        yrange = nrow;
    }

    foreach (dir; S) {
        int nx = x;
        int ny = y;
        if (dir == 'R') {
            nx = col[y].upperBound(tuple(xrange[0]-1, xrange[0]-1)).front[1] + 1;
        } else if (dir == 'L') {
            nx = col[y].lowerBound(tuple(xrange[1]+1, xrange[1]+1)).back[0] - 1;
        } else if (dir == 'U') {
            ny = row[x].upperBound(tuple(yrange[0]-1, yrange[0]-1)).front[1] + 1;
        } else {
            ny = row[x].lowerBound(tuple(yrange[1]+1, yrange[1]+1)).back[0] - 1;
        }
        x = nx;
        y = ny;
        insert(x, y);
    }

    writeln(x - N, " ", y - N);
}

Submission Info

Judge Result