a529: 大熊的寵物收養所
Tags :
Accepted rate : 14人/19人 ( 74% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-12-29 08:51

Content

阿狸想為自己領養一隻寵物。
寵物收養所的老闆是阿狸的好朋友大熊。大熊當然願意幫助阿狸,但需要聰明的阿狸為他解決一些問題。
大熊的收養所提供兩種服務:收養被主人遺棄的寵物和讓新的主人領養這些寵物。
每個在收養所的寵物都有一個特點值。同樣,每個領養者希望領養的寵物也有一個特點值。
1.如果一個領養者希望領養的寵物的特點值為a,那麼它將會領養一隻目前未被領養的寵物中特點值最接近a的一隻寵物。如果存在兩隻寵物他們的特點值分別為a-b和a+b,那麼領養者將會領養特點值為a-b的那隻寵物。
2.如果某寵物的特點值為a,存在兩個領養者他們希望領養寵物的特點值分別為a-b和a+b,那麼特點值為a-b的那個領養者將成功領養該寵物。
一個領養者領養了一個特點值為a的寵物,而它本身希望領養的寵物的特點值為b,那麼這個領養者的不滿意程度為abs(a-b)。
大熊將一年中領養者和被收養寵物到來收養所的情況給了阿狸,希望阿狸計算所有收養了寵物的領養者的不滿意程度的總和。這一年初始時,收養所裡面既沒有 寵物,也沒有領養者。
經過以上三道題你已經明白,阿狸總會把棘手的問題交給你來處理……

Input

第一行為一個正整數n,表示一年當中來到收養所的寵物和領養者的總數。接下來的n行,按到來時間的先後順序描述了一年當中來到收養所的寵物和領養者的情況。每行有兩個正整數a, b,其中a=0表示寵物,a=1表示領養者,b表示寵物的特點值或是領養者希望領養寵物的特點值。 (同一時間呆在收養所中的,要么全是寵物,要么全是領養者,這些寵物和領養者的個數不會超過10000個)

Output

僅有一個正整數,表示一年當中所有收養了寵物的領養者的不滿意程度的總和mod 1000000以後的結果。

Sample Input #1
5
0 2
0 4
1 3
1 2
1 5
Sample Output #1
3
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (33%): 1.0s , <1K
不公開 測資點#1 (33%): 1.0s , <1K
不公開 測資點#2 (34%): 1.0s , <1K
Hint :
Tags:
出處:
[管理者:
xllin@g.puic... (Emily Lin)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」