# PBinfo #3003 – Intersectie – Rezolvare C++

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

## Enunț

Cerința
Pe un cerc sunt așezate echidistant N puncte, etichetate în sensul acelor de ceas cu 1, 2, 3, …, N.
Se dau M intervale de forma [a, b] și T interogări de forma P Q.

Pentru fiecare interogare [P, Q] să se verifice dacă este adevărat sau fals că intersecția tuturor intervalelor care au puncte comune cu [P, Q] include intervalul [P, Q]. 

Date de intrare
Fișierul de intrare intersectie.in conține pe primul rând numerele N, M și T. Pe următoarele M rânduri sunt scrise câte două numere naturale a b, separate prin spațiu, reprezentând capetele celor M intervale date. Pe următoarele T rânduri sunt scrise câte două numere naturale P Q, separate prin spațiu, reprezentând capetele celor T intervale de interogare date.

Date de ieșire
În fișierul de ieșire intersectie.out pe primele T rânduri este scris un număr natural: 1 dacă răspunsul la interogare este adevărat, respectiv 0 dacă răspunsul este fals.

Restricții și precizări

2 ≤ N ≤ 1.000.000.000
1 ≤ M ≤ 100.000
1 ≤ T ≤ 100.000
1 ≤ P ≤ N, 1 ≤ Q ≤ N, P și Q sunt etichete date în sensul acelor de ceas
1 ≤ a ≤ N, 1 ≤ b ≤ N, a și b sunt etichete date în sensul acelor de ceas
Dacă x = y, atunci [x, y] este un interval care conține doar numărul x
Pentru 30% din teste 1 ≤ M ≤ 1000 și 1 ≤ T ≤ 10.000
Pentru 30% din teste 1 ≤ N ≤ 1.000.000

Exemplu:
intersectie.in

5 3 3
2 3
5 1
5 5
4 4
3 5
1 1
intersectie.out

0
0
1
Explicație
Intervalul [4,4] din interogarea 1 nu se intersectează cu nici unul din cele trei intervale date [2,3], [5,1], [5;5]. Răspuns 0. 
Intervalul [3,5] din interogarea 2 se intersectează cu [2,3], [5,1], [5,5]. Intersecția acestora este vidă. Răspuns 0.
Intervalul [1,1] din interogarea 3 se intersectează doar cu [5,1]. Intersecția intervalelor care conțin pe [1,1] este [5,1]. Răspuns 1.

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
using namespace std;
ifstream in("intersectie.in");
ofstream out("intersectie.out");
int n,m,i,t,x,y,nri,nrs,St[200005],Dr[200005];
pair<int,int> I[200005];
int checkin(int val)
{
    int i,rez=0;
    for(i=17;i>=0;i--)
        if(rez+(1<<i)<=nrs && I[rez+(1<<i)].first<=val)
            rez=rez+(1<<i);
    return (rez!=0 && I[rez].second>=val);
}
int srcst(int val)
{
    int i,rez=0;
    for(i=17;i>=0;i--)
        if(rez+(1<<i)<nri && St[rez+(1<<i)]<val)
            rez=rez+(1<<i);
    return St[rez+1];
}
int srcdr(int val)
{
    int i,rez=0;
    for(i=17;i>=0;i--)
        if(rez+(1<<i)<nri && Dr[rez+(1<<i)]<val)
            rez=rez+(1<<i);
    return Dr[rez+1];
}
int main()
{
    in>>n>>m>>t;
    for(i=1; i<=m; i++)
    {
        in>>x>>y;
        if(x<=y)
        {
            nri++;
            St[nri]=x;
            Dr[nri]=y;
            I[nri]={x,y};
        }
        else
        {
            nri++;
            St[nri]=x;
            Dr[nri]=n+1;
            I[nri]={x,n+1};
            nri++;
            St[nri]=0;
            Dr[nri]=y;
            I[nri]= {0,y};
        }
    }
    St[++nri]=n+1;
    Dr[nri]=n+1;
    sort(St+1,St+nri+1);
    sort(Dr+1,Dr+nri+1);
    sort(I+1,I+nri+1);
    I[0]={-1,-1};
    for(i=1;i<=nri;i++)
    {
        if(I[nrs].second<I[i].first)
        {
            nrs++;
            I[nrs]=I[i];
        }
        else
            I[nrs].second=max(I[nrs].second,I[i].second);
    }
    for(i=1;i<=t;i++)
    {
        in>>x>>y;
        if(x==y)
        {
            out<<"1\n";
            continue;
        }
        if(x<y)
        {
            if(srcst(x+1)>y && srcdr(x)>=y)
                out<<"1\n";
            else
                out<<"0\n";
            continue;
        }
        if(srcst(x+1)>n && srcdr(x)>n && srcst(1)>y && srcdr(0)>=y)
            out<<"1\n";
        else
            out<<"0\n";
    }
    return 0;
}
```

## Resurse

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