#include "bits/stdc++.h"
using namespace std;
struct Nodo{
long long Suma, Uneado;
};
map<long long, Nodo> _rbol;
long long Consulta(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
if(Izquierda >= Inicio and Derecha <= Final) return _rbol[Posici_n].Suma;
else if(Izquierda > Final or Derecha < Inicio) return 0;
else {
long long Promedio = (Izquierda + Derecha) / 2;
if(_rbol[Posici_n].Uneado == 1 and Izquierda != Derecha){
_rbol[Posici_n * 2].Suma = Promedio - Izquierda + 1;
_rbol[Posici_n * 2 + 1].Suma = Derecha - (Promedio + 1) + 1;
_rbol[Posici_n * 2].Uneado = 1;
_rbol[Posici_n * 2 + 1].Uneado = 1;
_rbol[Posici_n].Uneado = 0;
}
return Consulta(Izquierda, Promedio, Posici_n * 2, Inicio, Final) + Consulta(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final);
}
}
void Actualizar(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
if(Izquierda >= Inicio and Derecha <= Final){
_rbol[Posici_n].Uneado = 1;
_rbol[Posici_n].Suma = Derecha - Izquierda + 1;
} else if(Izquierda > Final or Derecha < Inicio) return;
else {
long long Promedio = (Izquierda + Derecha) / 2;
if(_rbol[Posici_n].Uneado == 1 and Izquierda != Derecha){
_rbol[Posici_n * 2].Suma = Promedio - Izquierda + 1;
_rbol[Posici_n * 2 + 1].Suma = Derecha - (Promedio + 1) + 1;
_rbol[Posici_n * 2].Uneado = 1;
_rbol[Posici_n * 2 + 1].Uneado = 1;
_rbol[Posici_n].Uneado = 0;
}
Actualizar(Izquierda, Promedio, Posici_n * 2, Inicio, Final);
Actualizar(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final);
_rbol[Posici_n].Suma = _rbol[Posici_n * 2].Suma + _rbol[Posici_n * 2 + 1].Suma;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
long long n, m;
cin>>m;
n = 10e6 + 5;
n--;
long long C = 0;
while(m--){
long long Tipo;
cin>>Tipo;
if(Tipo == 1){
long long l, r;
cin>>l>>r;
l--;
r--;
long long Consultado = Consulta(0, n, 1, l + C, r + C);
C += Consultado;
cout<<Consultado<<"\n";
} else {
long long l, r;
cin>>l>>r;
l--;
r--;
Actualizar(0, n, 1, l + C, r + C);
}
/*for(auto i: _rbol) cout<<i.Suma<<" ";
cout<<"\n";
for(auto i: _rbol) cout<<i.Uneado<<" ";
cout<<"\n";*/
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
