oj.uz

Submission #901643

# Submission time Handle Problem Language Result Execution time Memory
901643 2024-01-09T20:17:36 Z Gabriel Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 0 ms 348 KB 
#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 = 10e9 + 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;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -