h074. Chinese Restaurant (Harder Version)
Tags : 前綴和 差分 掃描線 線段 線段樹
Accepted rate : 1人/3人 ( 33% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-25 17:37

Content

有 $n$ 個人,編號 $0$ ~ $n-1$,圍坐在一個圓桌旁,並且相鄰的兩個人的間距都是相等的。

一開始,第 $i$ 個人的面前有餐點 $p_i (0 \leq p_i \leq n-1)$。
你可以在開始用餐前任意地旋轉圓桌,假如你旋轉了一個餐點的距離,本來在第 $i$ 個人的面前的餐點會變成在第 $(i+1) \mod n$ 個人面前。

每個人都有一個可以夾菜的距離,第 $i$ 個人可以夾菜的距離是 $c_i$,表是他可以吃到順時鐘或逆時鐘方向距離 $c_i$ 道餐點以內的所有餐點。 
例子:有 $10$ 個人,第 $5$ 個人的夾菜距離是 $2$,表示他可以吃到位置 $[5-2, 5+2]$ = $[3, 7]$ 範圍的菜。

已知第 $i$ 個人最喜歡的餐點是編號 $i$ 的餐點,請在開始用餐前找到最好的圓桌旋轉方式(開始用餐用就不能再旋轉圓桌),讓盡可能多人能夾到自己喜歡吃的餐點。
輸出最多有幾個人可以夾到自己喜歡吃的餐點。

Input

輸入的第一行有一個非負整數 $n (1 \leq n \leq 200000)$,表示人數。

接下來有 $n$ 行,第 $i+1$ 行有兩個數字 $p_i (0\leq p_i < n)$ 和 $c_i \leq (n-1)/2$ 分別表示編號 $i$ 的人面前一開始的餐點編號以及第 $i$ 個人的夾菜距離。

Output

輸出一個整數表示在最好的旋轉方式下最多有多少人可以夾到自己喜歡的餐點。

Sample Input #1
4
1 1
2 1
0 1
3 1
Sample Output #1
4
Sample Input #2
 10
 3 1
 9 2
 6 1
 1 2
 7 0
 2 1
 8 2
 0 2
 5 1
 4 1
Sample Output #2
5
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 2.0s , <10M
公開 測資點#1 (20%): 2.0s , <10M
公開 測資點#2 (20%): 2.0s , <10M
公開 測資點#3 (20%): 2.0s , <10M
公開 測資點#4 (20%): 2.0s , <10M
Hint :
Tags:
前綴和 差分 掃描線 線段 線段樹
出處:
AtCoderABC_268C [管理者: cthbst(吳宗達) ]


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