Rezolvare completă PbInfo #2434 tnia

Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m.
Matricea dată are o formă particulară, astfel că pentru fiecare coloană i de la 1 la n toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul [1, h[i]] și în rest valoarea 0. Valorile h[i] sunt numere naturale date în ordine crescătoare (h[i-1] ≤ h[i], 1 ≤ i ≤ n).

Cerința

Să se răspundă la q întrebări de forma: dându-se numerele A, B, C, D se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colțul stânga-jos în coloana A și linia B, iar colțul dreapta-sus în coloana C și linia D.

Date de intrare

Fișierul de intrare este tnia.in.

  • pe prima linie se găsesc două numere naturale n și m despărțite printr-un spațiu, cu semnificația de mai sus;
  • pe a doua linie sunt cele n elemente h[i] ale vectorului despărțite prin câte un spațiu;
  • pe a treia linie este un număr natural q ce reprezintă numărul de întrebări;
  • pe următoarele q linii se găsesc câte patru numere A, B, C, D cu semnificația de mai sus, despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire tnia.out va conține q linii reprezentând răspunsul pentru fiecare întrebare.

Restricții și precizări

  • 0 ≤ h[i] ≤ m, 1 ≤ n ≤ 100 000
  • 1 ≤ q ≤ 100 000, 1 ≤ m ≤ 1 000 000 000
  • Pentru 15 puncte: n, m, q ≤ 100
  • Pentru alte 16 puncte: n, m, q ≤ 3000
  • Pentru alte 16 puncte: n ≤ 100 000, m ≤ 1000 000 000, q ≤ 100
  • În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru testul din exemplu.

Exemplu

tnia.in

5 10 
2 3 7 8 10 
5 
1 1 5 10 
2 5 4 7 
3 2 3 6 
3 8 3 10 
3 2 3 10

tnia.out

30
6 
5 
0 
6

Explicație

Zona dreptunghiulară având colțul stânga-jos la coloana 1 și linia 1 și colțul dreapta-sus la coloana 5 și linia 10 are suma elementelor 30. Analog, pentru celelalte patru întrebări, răspunsurile corecte sunt: 6, 5, 0 și 6.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema tnia:

// O(N Log N)

#include<stdio.h>
#include<algorithm>
using namespace std;

#define x first
#define y second
#define NMAX 100005

int height[NMAX], n, m, q;
long long partial_sums[NMAX];
pair<int, int> downL, topR;

inline int binarySearch(int left, int right, int value) {
    int mid, answer = left - 1;
    while(left <= right) {
        mid = (left + right) / 2;
        if(height[mid] < value) {
            answer = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    return answer;
}

int main () {

    freopen("tnia.in","r",stdin);
    freopen("tnia.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        scanf("%d",&height[i]);

    for(int i = 1; i <= n; i++)
        partial_sums[i] = partial_sums[i - 1] + height[i];

    scanf("%d",&q);
    for(int i = 1; i <= q; i++) {
        scanf("%d%d%d%d", &downL.x, &downL.y, &topR.x, &topR.y);
        int poz1 = binarySearch(downL.x, topR.x, downL.y);
        int poz2 = binarySearch(downL.x, topR.x, topR.y);

      //  printf("am obtinut %d %d\n", poz1, poz2);

        printf("%lld\n", partial_sums[poz2] - partial_sums[poz1] - ((long long)poz2 - poz1) * (downL.y - 1)
                         + ((long long)topR.x - poz2) * (topR.y - downL.y + 1));
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2434 tnia

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2434 tnia de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!