# PBinfo #4711 – unudoi12 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Se consideră doi vectori a = a[1], a[2], ..., a[n] și b = b[1], b[2], ..., b[m] de numere naturale. Se construiește matricea c având n linii și m coloane, în care c[i][j] = 1 dacă a[i] ≤ b[j], sau c[i][j] = 2 dacă a[i] > b[j]. De exemplu, pentru a = 2, 7, 3, 5 și b = 4, 5, 0, 1, 6 se obține matricea c de mai jos:

1 1 2 2 1
2 2 2 2 2
1 1 2 2 1
2 1 2 2 1

Această matrice are trei linii distincte, deoarece liniile 1 și 3 sunt identice.

Cerința
Să se determine numărul liniilor distincte din matricea c.

Date de intrare
Fișierul de intrare unudoi.in conține pe prima linie numerele n și m, separate printr-un spațiu. Pe a doua linie, separate prin câte un spațiu, se află numerele naturale a[1], a[2], ..., a[n]. Pe a treia linie, separate prin câte un spațiu, se află numerele naturale b[1], b[2], ..., b[m].

Date de ieșire
Fișierul de ieșire unudoi.out va conține pe prima linie un singur număr natural reprezentând numărul liniilor distincte din matrice.

Restricții și precizări

3 ≤ n, m ≤ 50.000
0 ≤ a[i], b[i] ≤ 1.000.000.000
Pentru 50% din teste, n, m ≤ 5000

Exemplu:
unudoi.in

4 5
2 7 3 5
4 5 0 1 6
unudoi.out

3

## Cod sursă C++

```cpp
/*
  implementare Adrian Panaete
  Complexitate O((m + n) log(m+n))
*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,i,k,x,sol,v[100010];
int main()
{
    freopen("unudoi.in","r",stdin);
    freopen("unudoi.out","w",stdout);
    scanf("%d%d",&n,&m);
    //pun toate valorile intr-un sir
    for(i=1;i<=n;i++){scanf("%d",&x);v[++k]=2*x;}//valorile x din a[] se inlocuiesc cu 2*x
    for(i=1;i<=m;i++){scanf("%d",&x);v[++k]=2*x+1;}//valorile din b[] se inlocuiesc cu 2*x+1
    //daca aveam a[i]<=b[i] acum am a[i]< b[i]
    //deoarece x<=y => 2x<=2y => 2x<2y+1
    //daca aveam a[i] > b [i] ramane valabil a[i] > b[i]
    // deoarece x > y => x>=y+1 => 2x >= 2y+2 2x > 2y+1
    //sortez valorile
    sort(v+1,v+k+1);
    // daca aveam a[i]=b[j] atunci a[i] apare inaintea lui b[j]
    //deci orice a este dupa b-urile strict mai mici si inaintea celor mai mari sau egale
    //toate a-urile situate consecutiv in sirul sortat dau linii identice
    //trebuie sa gasesc numarul "platourilor" formate numai din a-uri deci platourile de valori pare
    // deci e suficient sa pastrez resturile modulo 2
    for(i=1;i<=k;i++)v[i]=v[i]%2;
    //gasesc secventele de 0 consecutive varificand de cate ori am un 0 precedat de un 1
    //pentru a nu pierde prima secventa pun v[0] = 1
    v[0]=1;
    for(i=1;i<=k;i++)if(v[i]==0&&v[i-1]==1)sol++;
    printf("%d\n",sol);
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4711)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4711/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4711/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)