제출 #1254940

#제출 시각아이디문제언어결과실행 시간메모리
1254940Mer123haba456원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define N lli(2e5)
#define MOD lli(1e9 + 7)
#define heps(v) v.begin(), v.end()
typedef long long int lli;
typedef vector<lli> vlli;
typedef pair<lli, lli> plli;
typedef vector<plli> vplli;
typedef pair<lli, plli> pplli;
typedef vector<pplli> vpplli;

lli n,m,k,q,t;
vlli vect;
lli sinir = 1e9;

struct Eleman{
    Eleman* sol = nullptr, *sag = nullptr;
    lli topl = 0;
    bool durum = 0;
};

void gunc(Eleman * v, lli l,lli r, lli istl, lli istr){
    if(istl <= l && r <= istr){
        v->durum = 1;
        v->topl = r - l + 1;
        return;
    }
    lli m = (l+r)/2;
    if(v->sol == nullptr)
        v->sol = new Eleman();
    if(v->sag == nullptr)
        v->sag = new Eleman();
    if(istr <= m)
        gunc(v->sol, l,m,istl,istr);
    else if(istl > m)
        gunc(v->sag, m+1,r,istl,istr);
    else{
        gunc(v->sol, l,m,istl,istr);
        gunc(v->sag, m+1,r,istl,istr);
    }
    v->topl = max(v->topl, v->sag->topl + v->sol->topl);
}

lli getir(Eleman *v, lli l,lli r,lli istl, lli istr){
    if(v == nullptr)
        return 0;
    if(v -> durum)
        return min(istr, r) - max(istl ,l) + 1;
    if(istl <= l && r <= istr)
        return v->topl;
    lli m = (l+r)/2;
    if(istr <= m)
        return getir(v->sol, l,m,istl,istr);
    else if(istl > m)
        return getir(v->sag, m+1,r,istl,istr);
    else
        return getir(v->sol, l,m,istl,istr) + getir(v->sag, m+1,r,istl,istr);
}

int main()
{
    fast_io
    ifstream inp;
    inp.open("f.in");
    ofstream out;
    out.open("f.out");
    inp >> t;
    lli onc = 0;
    Eleman* kok = new Eleman();
    while(t--){
        inp >> q >> n >> m;
        n+= onc;
        m+=onc;
        if(q == 1){
            onc = getir(kok, 0, sinir, n,m);
            out << onc << endl;
        }else{
            gunc(kok, 0, sinir, n, m);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...