Răspuns:
Problema este destul de usoara, se rezolva folosind smenul lui mars:
Pentru un interval st, dr, se adauga 1 pe pozitia st( atunci cand intra ) si -1 pe pozitia dr ( atunci cand iese ) intr-un vector
Dupa ce am facut asta pentru fiecare interval, parcurgem vectorul si creem o suma partiala: v[i] += v[i - 1]
Acum, int v[i] o sa avem cati clienti au fost in magazin in momentul i
ex:
pentru un interval de genul 3 8 vectorul va arata cceva de genul:
0010000-1...
Iar apoi, dupa suma partiala, vectorul arata:
00111110...
Observi ca intervalul [5,8) este plin de 1, asa cum trebuia.
Se numara apoi cati de 0 sunt in intervalul total [t1,t1)
const int TMAX = 10000;
int v[TMAX + 1];
int main() {
int n, i, a, b, t1, t2, zero;
cin >> n >> t1 >> t2;
for ( i = 0; i < n; i ++ ) {
cin >> a >> b;
v[a] ++;
v[b] --;
}
zero = 0;
for ( i = t1; i < t2; i ++ ) {
v[i] += v[i - 1];
if ( v[i] == 0 )
zero ++;
}
cout << zero;
return 0;
}
Explicație:
