transport

Time limit: 0.55s
Memory limit: 256MB
Input: transport.in
Output: transport.out

Anul 1905

Un stat din America de Sud și-a propus investiții majore în infrastructura feroviară. Brazilianul Badinho este managerul unei companii de transport feroviar pe o magistrală importantă. De-a lungul magistralei se află NN stații, numerotate de la 11 la NN. Fiecărei stații îi corespunde un număr XiX_i care reprezintă numărul de kilometri de la începutul magistralei până la stația ii (X1=0X_1 = 0). Pentru simplitate Badinho reprezintă magistrala ca o dreaptă, iar stațiile ca puncte pe dreapta respectivă, stația ii aflându-se la coordonata XiX_i.

O rută reprezintă o submulțime de cel puțin 2 stații dintre cele NN, cu semnificația că în aceste stații se vor face opriri. Orice rută operată de Badinho are 2 stații numite capete, definite ca fiind cea mai apropiată stație, inclusă în rută, de începutul magistralei respectiv cea mai îndepărtată stație, inclusă în rută, de începutul magistralei.

Compania lui Badinho va primi o subvenție pentru deschiderea unei noi rute, care va fi proporțională cu lungimea rutei deschise. Mai exact, Badinho va primi CC reali (realul este moneda națională a Braziliei) pentru fiecare kilometru din noua rută. Lungimea rutei se definește ca fiind distanța dintre capete.

Badinho poate deschide două tipuri de rute:

  • Regio — se fac opriri în toate stațiile dintre cele două capete
  • Expres — unele stații dintre cele două capete pot fi traversate fără a opri în ele

Pentru a deschide o rută Badinho trebuie să construiască câte un depou în capetele rutei respective. Costul pentru a construi un depou în stația ii este DiD_i reali.

Știind că Badinho trebuie să cheltuiască întreaga sumă pe care ar primi-o dintr-o subvenție, să se determine:

  1. Numărul de moduri de a deschide o rută de tip Regio, modulo 109+7\text{modulo }10^9 + 7
  2. Numărul de moduri de a deschide o rută de tip Expres, modulo 109+7\text{modulo }10^9 + 7

Date de intrare

În fișierul transport.in se află:

  • Pe prima linie tipul cerinței TT, care poate avea valoarea 11 sau 22.
  • Pe a doua linie NN și CC, separate printr-un spațiu, reprezentând numărul de stații, respectiv suma primită per kilometru ca subvenție.
  • Pe următoarele NN linii, pe linia i+2i + 2 se află câte o pereche XiX_i și DiD_i, separate printr-un spațiu, reprezentând distanța la care se află stația ii față de începutul magistralei, respectiv costul de a contrui un depou în stația ii.

Date de ieșire

În fișierul transport.out se va afișa:

  • Dacă T=1T = 1, numărul de moduri de a deschide o rută de tip Regio, modulo 109+7\text{modulo }10^9 + 7
  • Dacă T=2T = 2, numărul de moduri de a deschide o rută de tip Expres, modulo 109+7\text{modulo }10^9 + 7

Restricții

  • Două rute se consideră distincte dacă diferă prin cel puțin o stație.
  • 2N200 0002 \leq N \leq 200\ 000, 1C1091 \leq C \leq 10^9
  • 0Xi,Di109  1iN0 \leq X_i, D_i \leq 10^9\ \forall \ 1 \leq i \leq N
  • X1=0X_1 = 0
  • Șirul XX este sortat strict crescător: Xi<Xj  1i<jNX_i \lt X_j \ \forall \ 1 \leq i \lt j \leq N.
  • Toate liniile de cale ferată ale magistralei sunt deja construite, singurele costuri pe care le va suporta Badinho sunt cele de construire a depourilor.

Subtask 1 (12 puncte)

  • T=1T = 1, N1 000N \leq 1\ 000

Subtask 2 (26 puncte)

  • T=1T = 1, N200 000N \leq 200\ 000

Subtask 3 (6 puncte)

  • T=2T = 2, N15N \leq 15

Subtask 4 (15 puncte)

  • T=2T = 2, N1 000N \leq 1\ 000

Subtask 5 (41 puncte)

  • T=2T = 2, N200 000N \leq 200\ 000

Exemplul 1

transport.in

1
5 1
0 2
1 1
3 10
4 15
6 4

transport.out

2

Explicație

Rutele posibile în condițiile cerinței 1 sunt: {1,2,3,4,5}\{1,2,3,4,5\}, {2,3,4,5}\{2,3,4,5\}.
Ruta {1,2,3,4,5}\{1,2,3,4,5\} conține opriri în stațiile 11, 22, 33, 44, 55. Stațiile 11 și 55 sunt cele 22 capete. Suma primită din subvenție este: 1(60)=61 \cdot (6-0) = 6 reali (606-0 reprezintă distanța dintre stația 11 și 55), iar costul de construire a celor 22 depouri e: 2+4=62+4 = 6 reali.

Exemplul 2

transport.in

2
5 1
0 2
1 1
3 10
4 15
6 4

transport.out

12

Explicație

Rutele posibile în condițiile cerinței 2 sunt: {1,5}\{1,5\}, {1,2,5}\{1,2,5\}, {1,3,5}\{1,3,5\}, {1,4,5}\{1,4,5\}, {1,2,3,5}\{1,2,3,5\}, {1,2,4,5}\{1,2,4,5\}, {1,3,4,5}\{1,3,4,5\}, {1,2,3,4,5}\{1,2,3,4,5\}, {2,5}\{2,5\}, {2,3,5}\{2,3,5\}, {2,4,5}\{2,4,5\}, {2,3,4,5}\{2,3,4,5\}.
Ruta {1,2,5}\{1,2,5\} conține opriri în stațiile 11, 22, 55. Stațiile 11 și 55 sunt cele 22 extreme. Suma primită din subvenție e: 1(60)=61 \cdot (6-0) = 6 reali, iar costul de construire a celor 22 depouri e: 2+4=62+4 = 6 reali.

Problem info

ID: 286

Editor: ezluci

Author:

Source: OJI 2022 X: Problema 3

Tags:

OJI 2022 X

Log in or sign up to be able to send submissions!