TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

segmenti.pas    1,260 b      izvorni kod rešenja
segmenti.cpp    998 b      izvorni kod rešenja
segmenti.tests.7z    4,275,031 b      test primeri
segmenti.solution.pdf    29,908 b      rešenje problema

zadatak: Segmenti

Dato je n segmenata i m tačaka na x-osi. Za svaku od datih m tačaka odrediti broj segmenata kojima ona pripada. Tačka x pripada segmentu [a, b] ako je axb.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom redu standradnog ulaza nalaze se dva prirodna broja n ≤ 105 i m ≤ 105 - broj segmenata i broj tačaka, redom. U sledećem redu se nalaze m brojeva razdvojenih razmakom - koordinate tačaka. U sledećih n redova se nalaze po dva broja razdvojena razmakom - leva i desna koordinata odgovarajućeg segmenta (leva koordinata je strogo manja od desne). Sve koordinate su prirodni brojevi ne veći od 109.

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) Na standardni izlaz za svaku tačku ispisati broj segmenata kojima ona pripada, svaki broj u posebnom redu i u redosledu kojim su tačke date na ulazu.

Primer 1.

standardni ulaz      standardni izlaz
3 4
5 1 8 9
6 7
4 9
2 5 
        
2
0
1
1
fajl: segmenti.pas
const
  MaxN = 100010;
  MaxM = 100010;

type
  Point = Record
    x : longint;
    t : longint;
    num : longint;
  end;

var
  a : array[0..2*MaxN + MaxM] of Point;
  sol : array[0..MaxM] of longint;
  n, m, i, sum : longint;
  x, y : Point;


procedure QS(l, r : longint);
var
  i, j: longint;
begin
  i := l; j := r; x := a[(l + r) DIV 2];
  repeat
    while ((a[i].x < x.x) or ((a[i].x = x.x) and (a[i].t > x.t))) do i := i + 1;
    while ((x.x < a[j].x) or ((x.x = a[j].x) and (x.t > a[j].t))) do j := j - 1;
    if (i <= j) then begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until (i > j);
  if (l < j) then QS(l, j);
  if (i < r) then QS(i, r);
end;

begin

   readln(n, m);
   for i := 0 to m - 1 do begin
     read(a[i].x);
     a[i].t := 0;
     a[i].num := i;
   end;
   for i := 0 to n - 1 do begin
     readln(a[m + 2*i].x, a[m + 2*i + 1].x);
     a[m + 2*i].t := 1;
     a[m + 2*i + 1].t := -1;
   end;

   QS(0, m + 2 * n - 1);
   sum := 0;
   for i := 0 to m + 2 * n - 1 do begin
     if (a[i].t = 0) then
       sol[ a[i].num ] := sum
     else
       sum := sum + a[i].t;
   end;

   for i := 0 to m - 1 do
     writeln(sol[i]);

end.
fajl: segmenti.cpp
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MaxN = 100010;
const int MaxM = 100010;


int n, m, sum;

struct Point {
  int x;      // type =  1 => levi kraj segmenta
  int type;    // type =  0 => jedna od m tacaka
  int num;    // type = -1 => desni kraj segmenta
};

Point a[2 * MaxN + MaxM];
int sol[MaxM];

bool cmp(Point A, Point B) {
  return ((A.x < B.x) || (A.x == B.x && A.type > B.type));
}

int main() {

  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d", &a[i].x);
    a[i].type = 0;
    a[i].num = i;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a[m + 2 * i].x, &a[m + 2 * i + 1].x);
    a[m + 2 * i].type = 1;  
    a[m + 2 * i + 1].type = -1; 
  }

  sort(a, a + m + 2 * n, cmp);

  sum = 0;
  for (int i = 0; i < m + 2 * n; i++) {
    if (a[i].type == 0) 
      sol[ a[i].num ] = sum;
    else 
      sum += a[i].type;
  }

  for (int i = 0; i < m; i++)
    printf("%d\n", sol[i]);

  return 0;
}