#include <iostream>
#include <stdio.h>
using namespace std;
const long long mxn = 2e6 + 10;
long long ro,pa[mxn] = {},lrp[mxn] = {},lch[mxn] = {},rch[mxn] = {},
lbo[mxn] = {},rbo[mxn] = {},nlbo[mxn] = {},nrbo[mxn] = {},rip[mxn] = {},ru = 1,
ans[mxn] = {};
long long fimi(long long l,long long r)
{
if(l < r)
return l;
return r;
}
long long fima(long long l,long long r)
{
if(l > r)
return l;
return r;
}
long long upd(long long fn)
{
rip[fn] = nrbo[fn] - nlbo[fn] + 1;
if(lch[fn] != -1)
{
rip[fn] += rip[lch[fn]];
lbo[fn] = lbo[lch[fn]];
}
else
{
lbo[fn] = nlbo[fn];
}
if(rch[fn] != -1)
{
rip[fn] += rip[rch[fn]];
rbo[fn] = rbo[rch[fn]];
}
else
{
rbo[fn] = nrbo[fn];
}
return 0;
}
long long utr(long long cn)
{
while(cn != -1)
{
upd(cn);
cn = pa[cn];
}
return 0;
}
//long long sply(long long cn)
//{
// long long fn,tn,f;
// if(ro == cn)
// {
// upd(cn);
// return 0;
// }
// fn = pa[cn];
// if(fn == ro)
// {
// pa[cn] = pa[fn];
// if(fn != ro)
// {
// if(lrp[fn] == -1)
// {
// rch[pa[fn]] = cn;
// }
// else
// {
// lch[pa[fn]] = cn;
// }
// }
// if(lrp[cn] == -1)
// {
// lrp[cn] = lrp[fn];
// rch[fn] = lch[cn];
// if(lch[cn] != -1)
// {
// pa[lch[cn]] = fn;
// lrp[lch[cn]] = -1;
// }
// lch[cn] = fn;
// pa[fn] = cn;
// lrp[fn] = 1;
// }
// else
// {
// lrp[cn] = lrp[fn];
// lch[fn] = rch[cn];
// if(rch[cn] != -1)
// {
// pa[rch[cn]] = fn;
// lrp[rch[cn]] = 1;
// }
// rch[cn] = fn;
// pa[fn] = cn;
// lrp[fn] = -1;
// }
// }
// else
// {
// tn = pa[fn];
// pa[cn] = pa[tn];
// if(tn != ro)
// {
// if(lrp[tn] == -1)
// {
// rch[pa[tn]] = cn;
// }
// else
// {
// lch[pa[tn]] = cn;
// }
// }
// if(lrp[cn] == -1)
// {
// if(lrp[fn] == -1)
// {
// lrp[cn] = lrp[tn];
// rch[tn] = lch[fn];
// if(lch[fn] != -1)
// {
// pa[lch[fn]] = tn;
// lrp[lch[fn]] = -1;
// }
// rch[fn] = lch[cn];
// if(lch[cn] != -1)
// {
// pa[lch[cn]] = fn;
// lrp[lch[cn]] = -1;
// }
// lch[fn] = tn;
// pa[tn] = fn;
// lrp[tn] = 1;
// lch[cn] = fn;
// pa[fn] = cn;
// lrp[fn] = 1;
// }
// else
// {
// lrp[cn] = lrp[tn];
// rch[fn] = lch[cn];
// if(lch[cn] != -1)
// {
// pa[lch[cn]] = fn;
// lrp[lch[cn]] = -1;
// }
// lch[tn] = rch[cn];
// if(rch[cn] != -1)
// {
// pa[rch[cn]] = tn;
// lrp[rch[cn]] = 1;
// }
// lch[cn] = fn;
// pa[fn] = cn;
// lrp[fn] = 1;
// rch[cn] = tn;
// pa[tn] = cn;
// lrp[tn] = -1;
// }
// }
// else
// {
// if(lrp[fn] == -1)
// {
// lrp[cn] = lrp[tn];
// rch[tn] = lch[cn];
// if(lch[cn] != -1)
// {
// pa[lch[cn]] = tn;
// lrp[lch[cn]] = -1;
// }
// lch[fn] = rch[cn];
// if(rch[cn] != -1)
// {
// pa[rch[cn]] = fn;
// lrp[rch[cn]] = 1;
// }
// lch[cn] = tn;
// pa[tn] = cn;
// lrp[tn] = 1;
// rch[cn] = fn;
// pa[fn] = cn;
// lrp[fn] = -1;
// }
// else
// {
// lrp[cn] = lrp[tn];
// lch[tn] = rch[fn];
// if(rch[fn] != -1)
// {
// pa[rch[fn]] = tn;
// lrp[rch[fn]] = 1;
// }
// lch[fn] = rch[cn];
// if(rch[cn] != -1)
// {
// pa[rch[cn]] = fn;
// lrp[rch[cn]] = 1;
// }
// rch[fn] = tn;
// pa[tn] = fn;
// lrp[tn] = -1;
// rch[cn] = fn;
// pa[fn] = cn;
// lrp[fn] = -1;
// }
// }
// upd(tn);
// }
// upd(fn);
// upd(cn);
// if(fn != ro && tn != ro)
// {
// sply(cn);
// }
// ro = cn;
// return 0;
//}
long long del(long long cn)
{
if(lch[cn] == -1)
{
if(rch[cn] == -1)
{
if(pa[cn] != -1)
{
if(lrp[cn] == -1)
{
rch[pa[cn]] = -1;
}
else
{
lch[pa[cn]] = -1;
}
}
// if(pa[cn] != -1)
// sply(pa[cn]);
utr(pa[cn]);
return pa[cn];
}
else
{
if(pa[cn] != -1)
{
if(lrp[cn] == -1)
{
rch[pa[cn]] = rch[cn];
}
else
{
lch[pa[cn]] = rch[cn];
}
}
else
{
ro = rch[cn];
}
lrp[rch[cn]] = lrp[cn];
pa[rch[cn]] = pa[cn];
// sply(rch[cn]);
utr(rch[cn]);
return rch[cn];
}
}
else
{
if(rch[cn] == -1)
{
if(pa[cn] != -1)
{
if(lrp[cn] == -1)
{
rch[pa[cn]] = lch[cn];
}
else
{
lch[pa[cn]] = lch[cn];
}
}
else
{
ro = lch[cn];
}
lrp[lch[cn]] = lrp[cn];
pa[lch[cn]] = pa[cn];
// sply(lch[cn]);
utr(lch[cn]);
return lch[cn];
}
else
{
long long fn = lch[cn],tn;
while(rch[fn] != -1)
{
fn = rch[fn];
}
tn = pa[fn];
if(tn == cn)
{
// if(lch[fn] != -1)
// {
lch[cn] = lch[fn];
// }
}
else
{
rch[tn] = lch[fn];
if(lch[fn] != -1)
{
lrp[lch[fn]] = -1;
}
}
if(lch[fn] != -1)
pa[lch[fn]] = tn;
// del(fn);
pa[fn] = pa[cn];
lrp[fn] = lrp[cn];
// if(lch[cn] != fn)
// {
lch[fn] = lch[cn];
// }
// else
// {
// lch[fn] = -1;
// }
rch[fn] = rch[cn];
if(lch[cn] != -1)
{
pa[lch[cn]] = fn;
}
if(rch[cn] != -1)
{
pa[rch[cn]] = fn;
}
if(pa[cn] != -1)
{
if(lrp[cn] == -1)
{
rch[pa[cn]] = fn;
}
else
{
lch[pa[cn]] = fn;
}
}
if(cn == ro)
{
ro = fn;
}
// if(tn != cn)
// sply(tn);
// sply(fn);
if(tn != cn)
utr(tn);
utr(fn);
return fn;
}
}
while(1)
printf("efef");
return -1;
}
long long ripe(long long cn,long long tl,long long tr)
{
long long fn;
if(nlbo[cn] > tr)
{
if(lch[cn] != -1)
{
ripe(lch[cn],tl,tr);
}
else
{
lch[cn] = ru;
lch[ru] = -1;
rch[ru] = -1;
pa[ru] = cn;
lrp[ru] = 1;
nlbo[ru] = tl;
nrbo[ru] = tr;
lbo[ru] = tl;
rbo[ru] = tr;
rip[ru] = tr-tl+1;
lbo[cn] = tl;
rip[cn] += rip[ru];
ru ++;
// sply(ru-1);
utr(ru-1);
}
}
else if(nrbo[cn] < tl)
{
if(rch[cn] != -1)
{
ripe(rch[cn],tl,tr);
}
else
{
rch[cn] = ru;
lch[ru] = -1;
rch[ru] = -1;
pa[ru] = cn;
lrp[ru] = -1;
nlbo[ru] = tl;
nrbo[ru] = tr;
lbo[ru] = tl;
rbo[ru] = tr;
rip[ru] = tr-tl+1;
rbo[cn] = tr;
rip[cn] += rip[ru];
ru ++;
// sply(ru-1);
utr(ru-1);
}
}
else
{
tl = fimi(tl,nlbo[cn]);
tr = fima(tr,nrbo[cn]);
fn = del(cn);
if(fn == -1)
{
ro = ru;
lch[ru] = -1;
rch[ru] = -1;
pa[ru] = -1;
lrp[ru] = 0;
nlbo[ru] = tl;
nrbo[ru] = tr;
lbo[ru] = tl;
rbo[ru] = tr;
rip[ru] = tr-tl+1;
ru ++;
// sply(ru-1);
utr(ru-1);
}
else
{
ripe(fn,tl,tr);
}
}
return 0;
}
long long getva(long long cn,long long tl,long long tr)
{
if(lbo[cn] > tr || rbo[cn] < tl)
{
return 0;
}
if(lbo[cn] >= tl && rbo[cn] <= tr)
{
return rip[cn];
}
long long cva = 0;
if(nlbo[cn] <= tl && nrbo[cn] >= tr)
{
cva += tr - tl + 1;
}
else if(nlbo[cn] >= tl && nrbo[cn] <= tr)
{
cva += nrbo[cn] - nlbo[cn] + 1;
}
else if(nrbo[cn] >= tl && nlbo[cn] < tl)
{
cva += nrbo[cn] - tl + 1;
}
else if(nlbo[cn] <= tr && nrbo[cn] > tr)
{
cva += tr - nlbo[cn] + 1;
}
if(lch[cn] != -1)
{
cva += getva(lch[cn],tl,tr);
}
if(rch[cn] != -1)
{
cva += getva(rch[cn],tl,tr);
}
return cva;
}
int main()
{
long long i,j,n,m,cl,cr,sta,cva,c = 0,cou = 0;
scanf("%lld",&n);
ro = -1;
for(i=0; i<n; i++)
{
scanf("%lld %lld %lld",&sta,&cl,&cr);
cl += c;
cr += c;
if(sta == -1)
{
break;
}
else if(sta == 1)
{
if(ro == -1)
{
cva = 0;
}
else
{
cva = getva(ro,cl,cr);
}
ans[cou] = cva;
cou ++;
// printf("%lld\n",cva);
c += cva;
}
else
{
if(ro == -1)
{
ro = ru;
lch[ru] = -1;
rch[ru] = -1;
pa[ru] = -1;
lrp[ru] = 0;
nlbo[ru] = cl;
nrbo[ru] = cr;
lbo[ru] = cl;
rbo[ru] = cr;
rip[ru] = cr-cl+1;
ru ++;
}
else
{
ripe(ro,cl,cr);
}
}
}
for(i=0; i<cou; i++)
{
printf("%lld\n",ans[i]);
}
return 0;
}
Compilation message
apple.cpp: In function 'int main()':
apple.cpp:486:17: warning: unused variable 'j' [-Wunused-variable]
486 | long long i,j,n,m,cl,cr,sta,cva,c = 0,cou = 0;
| ^
apple.cpp:486:21: warning: unused variable 'm' [-Wunused-variable]
486 | long long i,j,n,m,cl,cr,sta,cva,c = 0,cou = 0;
| ^
apple.cpp:487:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
487 | scanf("%lld",&n);
| ~~~~~^~~~~~~~~~~
apple.cpp:491:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
491 | scanf("%lld %lld %lld",&sta,&cl,&cr);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
