AT_arc044_c.[ARC044C] ビーム

题意简述

有一个 $H\times W$ 的网格，左下角为 $\left(1,1\right)$，右上角为 $\left(W,H\right)$。

这个网格很危险，会有 $Q$ 束光束飞来，光束用形如 $\left(T,D,X\right)$ 的三元组给出，$T$ 表示光束到来的时间，$D$ 表示方向（$0$ 为垂直，$1$ 为水平），$X$ 为坐标。例如 $\left(t,1,a\right)$ 表示第 $t$ 秒有一束光束会通过所有坐标为 $\left(i,a\right)\left(1\le i\le W\right)$ 的格子。

高桥君已知所有光束来袭的信息，他要让自己不会被光束击中。他可以自由选择初始位置，且结束位置没有限制，一秒可以移动任意次（每次可以横向或竖向移动一步），但不能走出网格。

请计算高桥君最少的移动次数。如果高桥君一定会碰到光束，则输出 $−1$。

第一行三个整数 $W,H,Q$。

之后 $Q$ 行，每行三个整数 $T_i,D_i,X_i$，表示每束光束。

一个整数表示答案（记得换行）。

$1\le W,H\le 10^5,0\le Q\le 10^5,1\le T_i\le 10^5,D_i\in\left\{0,1\right\}$，当 $D_i=0$ 时 $1\le X_i\le W$；当 $D_i=1$ 时 $1\le X_i\le H$，$\forall i\ne j,\left(T_i,D_i,X_i\right)\ne\left(T_j,D_j,X_j\right)$。

Y204335翻译