No.1795 AtCoder Heuristic Rating coloring
タグ : / 解いたユーザー数 103
作問者 :
harurun
/ テスター :
Kanten4205
This problem is the problem for day 24 of Advent Calendar Contest Advent Calendar 2021.
Story
AtCoder Heuristic Rating coloring is a user script that colors the usernames on the AtCoder Heuristic Contest standings according to their heuristic ratings.
Each time an AtCoder Heuristic Contest ends, the ratings in this script are updated using an update script.
Today's contest has ended and harurun tried to update the ratings, but he accidentally deleted the update script and is in trouble.
Please write an update script and help harurun.
Problem Statement
Up to yesterday, $N$ people have participated in AtCoder Heuristic Contest.
Today, a new AtCoder Heuristic Contest was held, and $M$ people participated.
You are given the usernames $S_i$ and ratings $A_i$ $(1≤i≤N)$ of the $N$ people before the contest, and the usernames $T_j$ and ratings $B_j$ $(1≤j≤M)$ of the $M$ people in this contest. Find the current rating of every user who has participated in at least one contest.
The current rating of each user is determined as follows.
If the user participated in this contest, it is their rating from this contest.
If the user did not participate in this contest, it is their rating before the contest.
Input
$N\ M$ $S_1\ A_1$ $\vdots$ $S_N\ A_N$ $T_1\ B_1$ $\vdots$ $T_M\ B_M$
Constraints
$0≤N≤5\times 10^4$
$1≤M≤5\times 10^4$
$2≤|S_i|,|T_i|≤16$
$1≤A_i≤9999 (1≤i≤N)$
$1≤B_i≤9999 (1≤i≤M)$
$N,M,A_i,B_i$ are all integers.
$S_i,T_i$ consist of lowercase English letters, uppercase English letters, digits, and
_(case-sensitive).$S_i\neq S_j (i\neq j)$
$T_i\neq T_j (i\neq j)$
If $S_i=T_j$, then $A_i≤B_j$
Output
Let $k$ be the number of users who have participated up to today. Output $k$ lines as follows, in lexicographical order of usernames.
On each line, output the username and the rating separated by a space. (See the samples for details.)
Sample
Sample 1
Input
2 2 user 30 harurun 10 harurun 100 user 9999
Output
harurun 100 user 9999
Output in lexicographical order of usernames.
Sample 2
Input
0 1 harurun 50
Output
harurun 50
There may be no participants up to yesterday.
Sample 3
Input
1 1 harurun 2000 Harurun 2000
Output
Harurun 2000 harurun 2000
Uppercase and lowercase letters are distinguished.
Sample 4
Input
63 63 pp 10 nn 20 dd 30 WW 40 00 50 22 60 77 70 vv 80 ll 90 FF 100 55 110 ii 120 II 130 kk 140 GG 150 NN 160 aa 170 rr 180 PP 190 zz 200 HH 210 66 220 DD 230 ee 240 SS 250 EE 260 jj 270 KK 280 TT 290 bb 300 44 310 RR 320 33 330 YY 340 11 350 oo 360 BB 370 hh 380 QQ 390 UU 400 mm 410 __ 420 MM 430 CC 440 ww 450 gg 460 88 470 OO 480 qq 490 LL 500 XX 510 JJ 520 AA 530 ff 540 VV 550 xx 560 ZZ 570 tt 580 yy 590 99 600 cc 610 uu 620 ss 630 QQ 390 CC 440 88 470 __ 420 WW 40 jj 270 33 330 RR 320 ff 540 kk 140 mm 410 KK 280 ii 120 TT 290 ee 240 00 50 55 110 AA 530 xx 560 XX 510 SS 250 11 350 66 220 vv 80 NN 160 gg 460 oo 360 UU 400 rr 180 tt 580 MM 430 yy 590 dd 30 DD 230 YY 340 cc 610 22 60 JJ 520 zz 200 ll 90 uu 620 99 600 hh 380 VV 550 PP 190 HH 210 nn 20 pp 10 44 310 qq 490 ss 630 GG 150 ZZ 570 aa 170 ww 450 bb 300 FF 100 BB 370 EE 260 LL 500 II 130 OO 480 77 70
Output
00 50 11 350 22 60 33 330 44 310 55 110 66 220 77 70 88 470 99 600 AA 530 BB 370 CC 440 DD 230 EE 260 FF 100 GG 150 HH 210 II 130 JJ 520 KK 280 LL 500 MM 430 NN 160 OO 480 PP 190 QQ 390 RR 320 SS 250 TT 290 UU 400 VV 550 WW 40 XX 510 YY 340 ZZ 570 __ 420 aa 170 bb 300 cc 610 dd 30 ee 240 ff 540 gg 460 hh 380 ii 120 jj 270 kk 140 ll 90 mm 410 nn 20 oo 360 pp 10 qq 490 rr 180 ss 630 tt 580 uu 620 vv 80 ww 450 xx 560 yy 590 zz 200
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。