#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 time | Memory | Grader output |
---|
Fetching results... |