問題一覧 > 通常問題

No.1795 AtCoder Heuristic Rating coloring

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 93
作問者 : harurunharurun / テスター : Kanten4205Kanten4205
2 ProblemId : 7303 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-16 08:08:14

この問題は Advent Calendar Contest Advent Calendar 2021 24日目の問題です。

ストーリー

AtCoder Heuristic Rating coloringはAtCoder Heuristic Contestの順位表のユーザー名をヒューリスティックのレーティングで色付けするユーザースクリプトです。

このスクリプトはAtCoder Heuristic Contestが終わる毎に更新スクリプトを用いてレーティングが更新されます。

今日のContestが終わりレーティングを更新しようとしましたが、harurun君は誤って更新スクリプトを削除してしまい困っています。

あなたが更新スクリプトを作って、harurun君を助けてあげてください。

問題文

AtCoder Heuristic Contestには 昨日までに $N$ 人が参加しています。

今日、新たにAtCoder Heuristic Contestが行われ、$M$ 人が参加しました。

コンテスト前の $N$ 人のユーザー名 $S_i$ と レーティング $A_i$ $(1≤i≤N)$ 、今回のコンテストの $M$ 人のユーザー名 $T_j$ とレーティング $B_j$ $(1≤j≤M)$ が与えられるので、1回以上コンテストに出たユーザーの今のレーティングを求めてください。

各ユーザーの今のレーティングは以下のように決定されます。

  • ユーザーが今回のコンテストに出ている場合、今回のコンテストのレーティングになる。

  • ユーザーが今回のコンテストに出ていない場合、コンテスト前のレーティングになる。

入力

$N\ M$
$S_1\ A_1$
$\vdots$
$S_N\ A_N$
$T_1\ B_1$
$\vdots$
$T_M\ B_M$

制約

  • $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$ は全て整数である。

  • $S_i,T_i$ は英小文字、英大文字、数字、_からなる(大文字小文字は区別される)。

  • $S_i\neq S_j (i\neq j)$

  • $T_i\neq T_j (i\neq j)$

  • $S_i=T_j$ のとき $A_i≤B_j$

出力

今日までに参加したユーザーの数を $k$ としたとき $k$ 行、ユーザー名の辞書順で以下のように出力してください。

各行ではユーザ名とレーティングの空白区切りで出力してください。(詳しくはサンプルをご覧ください。)

サンプル

サンプル1
入力
2 2
user 30  
harurun 10
harurun 100
user 9999
出力
harurun 100
user 9999

ユーザー名の辞書順で出力してください。

サンプル2
入力
0 1
harurun 50
出力
harurun 50

昨日までの参加者がいないこともあります。

サンプル3
入力
1 1
harurun 2000
Harurun 2000
出力
Harurun 2000
harurun 2000

大文字小文字は区別されます。

サンプル4
入力
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
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。