Fişierul intrare/ieşire:nomem.in, nomem.outSursăLot Cluj 2009, Baraj 6
AutorCatalin-Stefan TiseanuAdăugată desima_cotizoSima Cotizo sima_cotizo
Timp execuţie pe test0.7 secLimită de memorie9216 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nomem

În urma unei afaceri necurate cu mafiotul Ivan, Lunasorab a suferit un accident suspect de maşină. Din această cauză el se confruntă cu o pierdere temporară a memoriei. Acest lucru este foarte neplăcut, deoarece el trebuia să facă inventarul moşiilor sale de creştere a găinilor. Aceastea au forma unui triunghi isoscel dreptunghic, cu catetele paralele cu axele de coordonate. Mai exact, suprafaţa pe care se găsesc moşiile lui Lunasorab poate fi modelată ca o matrice pătratică de N linii şi N coloane (cu liniile şi coloanele numerotate de la 1 la N) de numere naturale, în fiecare pătrat de dimensiuni 1 × 1 găsindu-se coeficientul de inteligenţă al unei găini. Un triunghi isoscel dreptunghic de catetă de lungime L cu originea pe linia x şi coloana y va conţine toate celulele din matrice de linie a şi coloană b cu a ≤ x şi b ≥ y şi cu |a – x| + |b - y| < L.

Pentru Lunasorab gradul de risc al unei moşii (reprezentată ca un triunghi isoscel dreptunghic definit ca mai sus) este dată de valoarea minimă a coeficientului de inteligenţă al unei găini de pe moşia respectivă.

Deoarece momentan Lunasorab nu stă prea bine cu memoria, el vă cere suma gradelor de risc ale tuturor moşiilor modulo 1 000 000 007.

Cerinţă

Ajutaţi-l pe Lunasorab să afle rapid suma tuturor gradelor de risc ale moşiilor sale.

Date de intrare

Pe prima linie a fişierului de intrare nomem.in se găsesc numerele N şi Q, separate prin câte un singur spaţiu, reprezentând dimensiunile matricii, respectiv numărul de moşii ale lui Lunasorab. Pe următoarele N linii, fiecare conţinând N elemente, urmează elementele matricii, separate prin câte un singur spaţiu. Următoarele Q linii conţin câte 3 numere L x y, separate prin câte un singur spaţiu reprezentând moşia cu originea în x y, de latură L.

Date de ieşire

În fişierul de ieşire nomem.out se va găsi un număr natural, reprezentând suma gradelor de risc ale tuturor moşiilor modulo 1 000 000 007.

Restricţii şi precizări

  • 1 ≤ N ≤ 1 000
  • 1 ≤ Q ≤ 1 000 000
  • 1 ≤ x, y, L ≤ N
  • O moşie se găseşte complet în interiorul unei matrici.
  • Gradul de inteligenţă al unei găini este cuprins între 0 şi 1 010 010 010.
  • În fişierul de intrare întrebările vor fi ordonate crescător după L.
  • Pot exista găini care nu aparţin niciunei moşii ale lui Lunasorab.
  • Pentru 20% din teste N = 200 şi Q = 100 000.
  • Pentru încă 20% din teste N = 300 şi Q = 400 000.
  • Pentru încă 20% din teste N = 700 şi Q = 1 000 000.
  • Lunasorab vă recomandă să parsaţi citirea pentru a avea mai mult timp ca să-l ajutaţi.

Exemplu

nomem.innomem.out
3 3
1 2 3
4 5 6
7 8 9
1 2 3
2 3 2
3 3 1
12

Explicaţie

Pentru prima întrebare răspunsul este 6, pentru a doua 5 iar pentru ultima 1. Dacă le adunăm şi facem restul împărţirii modulo 1 000 000 007 obţinem 12.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content