| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 553363 | 2022-04-25T14:58:48 Z | Amylopectin | 원숭이와 사과 나무 (IZhO12_apple) | C++14 | 1 ms | 340 KB |
#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] = {},memcou = 0,ru = 0,
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 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]);
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]);
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]);
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
{
if(lch[fn] != -1)
{
rch[tn] = lch[fn];
lrp[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);
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);
}
}
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);
}
}
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);
}
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("%d\n",ans[i]);
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Incorrect | 0 ms | 340 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |