Codeforces 849 D. Rooter's Song （技巧）

Codeforces 849 D. Rooter's Song （技巧）

Description

Input

The first line of input contains three space-separated positive integers n, w and h (1 ≤ n ≤ 100 000, 2 ≤ w, h ≤ 100 000) — the number of dancers and the width and height of the stage, respectively.The following n lines each describes a dancer: the i-th among them contains three space-separated integers gi, pi, and ti (1 ≤ gi ≤ 2, 1 ≤ pi ≤ 99 999, 0 ≤ ti ≤ 100 000), describing a dancer’s group gi (gi = 1 — vertical, gi = 2 — horizontal), position, and waiting time. If gi = 1 then pi = xi; otherwise pi = yi. It’s guaranteed that 1 ≤ xi ≤ w - 1 and 1 ≤ yi ≤ h - 1. It is guaranteed that no two dancers have the same group, position and waiting time at the same time.

Output

Output n lines, the i-th of which contains two space-separated integers (xi, yi) — the stopping position of the i-th dancer in the input.

Examples input

8 10 81 1 101 4 131 7 11 8 22 2 02 5 142 6 02 6 1

Examples output

4 810 58 810 610 21 87 810 6

Hint

样例解释

题意

场上有 n

思路

设有一点 a 在 x 轴的坐标为 (x1,0) ， t1

设有一点 b 在 y 轴的坐标为 (0,y2) ， t2

若 a,b 相遇，则 y2+t1=x1+t2 ，即 x1−t1=y2−t2

我们来看样例中的 (1,1,10),(1,4,13),(2,5,14) 这三个点，显然理论无影响下 (2,5,14)

从 hint 中我们可以看出， (1,1,10) 在与 (2,5,14) 相遇后改变了移动方向，随后又与 (1,4,13)

我们称这样的碰撞为方向的传递，即 (2,5,14) 将其移动方向传递给了 (1,4,13)

显然，我们首先应该对 x 轴与 y

对于 x 轴每一点的时刻 xi−ti

而对 y 轴的这些点中，我们去查找队列 yi−ti

若为空，则说明没有任何一个点会影响该点的运动否则将当前点的移动状态转移给队列尾部的那一个点，然后将自身加入该队列的首部。（因为最后只有自身与队尾改变了移动方向）

所有最终出现在 x=w 上点的坐标这样就可以确定了，同理出现在 y=h

AC 代码

#includeusing namespace std;const int maxn = 1e5+10;typedef __int64 LL;typedef map::iterator MPIT;map mapp;int n,w,h;int ax[maxn],ay[maxn],tmp[maxn];struct node{ int gg,pp,tt,id; bool operator<(const node &x)const { return ppsecond.empty()) tmp[i]=i; else { tmp[i]=it->second.back(); it->second.pop_back(); it->second.push_front(i); } } mapp.clear();}void solve(){ sort(a+1,a+n+1); call(1,2); call(2,1); for(int i=1; i<=n; i++) if(a[i].gg==1) { ax[a[tmp[i]].id]=a[i].pp; ay[a[tmp[i]].id]=h; } else { ax[a[tmp[i]].id]=w; ay[a[tmp[i]].id]=a[i].pp; } for(int i=1; i<=n; i++) cout<>n>>w>>h; for(int i=1; i<=n; i++) cin>>a[i].gg>>a[i].pp>>a[i].tt,a[i].id=i; solve(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。