APIO2018 日本語問題文(オリジナル翻訳)

1 New home

原本

Wu-Fu Street is an incredibly straight street that can be described as a one-dimensional number line,and each building’s location on the　street can be represented with just one number. Xiao-Ming the Time Traveler knows that there are n stores of k store-types that had　opened, has opened, or will open on the street. The i-th store can be described with four integers: xi, ti, ai, bi, representing the store’s location,the store’s type, the year when it starts its business, and the year when it is closed. Xiao-Ming the Time Traveler wants to choose a certain year and a certain location on Wu-Fu Street to live in. He has narrowed down his preference list to q location-year pairs. The i-th pair can be described with two integers: li, yi, representing the location and the year of the pair. Now he wants to evaluate the lifequality of these pairs. He defines the inconvenience index of a location-year pair to be the inaccessibility of the most inaccessible store-type of that pair. The inaccessibility of a location-year pair to store-type tis defined as the distance from the location to the nearest type-t store that is open in the year. We say the i-th store is open in the year y if ai ≤ y ≤ bi. Note that in some years, Wu-Fu Street may not have all the k store-types on it. In that case, the inconvenience index is defined as −1. Your task is to help Xiao-Ming find out the inconvenience index of each location-year pair.

問題文

通りに見立てた数直線上にn個の店がある。各店の位置(x座標)はx_i、タイプはt_iであり、a_i年からb_i年までオープンしている。店のタイプはk種類である。
タイムトラベラーは自分が住む場所と時間の候補のペアをq個用意した。各ペアの場所はl_i、年はy_iである。

各候補の生活の質は次のように定義される。
1. その年に営業していない店のタイプが存在するとき、-1
2. すべてのタイプの店が営業しているとき、その場所から一番近い各タイプの店との距離の最大値

各候補について、生活の質を答えよ。

制約

  • 1 <= n,q <= 3*105
  • 1 <= t_i <= k <= n
  • 1 <= x_i, a_i, b_i, l_i, t_i <= 108

2 Circle selection

3 Duathlon

原本

The Byteburg’s street network consists of n intersections linked by m two-way street segments. Recently, the Byteburg was chosen to host the upcoming duathlon championship. This competition consists of two legs: a running leg, followed by a cycling leg. The route for the competition should be constructed in the following way. First, three distinct intersections s, c, and f should be chosen for start, change and finish stations. Then the route for the competition should be built. The route should start in s, go through c and end in f. For safety reasons, the route should visit each intersection at most once. Before planning the route, the mayor wants to calculate the number of ways to choose intersections s, c, and f in such a way that it is possible to build the route for them. Help him to calculate this number.

問題文

n個の交差点のm個の道路からなる街がある。各道路は交差点v_iとu_iを結ぶ。Duathlonはトライアスロンの簡易版みたいなもので、マラソンの後にサイクリングをする競技である。

市長は競技のルートを考えている。各ルートはスタート地点s、競技変更地点c、終了地点fからなる。安全のため各交差点は1度しか通ることができない。
市長はルートを考えるにあたって、ルートを構築することが可能な(s,c,f)の組の個数を求めることにした。

制約

  • 1 <= n <= 105
  • 1 <= m <= 2*105