| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 373830 | Bench0310 | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node;
using twoNodes=array<Node*,2>;
struct Node
{
int a,c;
int val;
int sum;
twoNodes kids;
Node *p;
Node *pathp;
Node(int _a,int _c,int _val){a=_a;c=_c;val=sum=_val;kids[0]=kids[1]=p=pathp=nullptr;}
};
int side(Node *me){return (me->p?(me->p->kids[1]==me):0);}
void recalc(Node *me)
{
if(!me) return;
me->sum=me->val;
for(Node *to:me->kids) if(to) me->sum+=to->sum;
}
void make_parent(Node *me,int id,Node *kid)
{
if(me) me->kids[id]=kid;
recalc(me);
if(kid) kid->p=me;
}
void unmake_parent(Node *me,int id)
{
make_parent(nullptr,0,me->kids[id]);
make_parent(me,id,nullptr);
}
void rotate_up(Node *me)
{
Node *p=me->p;
int id=side(me);
if(!p->p) swap(me->pathp,p->pathp);
make_parent(p->p,side(p),me);
make_parent(p,id,me->kids[id^1]);
make_parent(me,id^1,p);
}
void splay(Node *me)
{
while(me->p)
{
if(me->p->p)
{
if(side(me)==side(me->p)) rotate_up(me->p);
else rotate_up(me);
}
rotate_up(me);
}
recalc(me);
}
void detach_path(Node *me)
{
if(me->kids[1]) me->kids[1]->pathp=me;
unmake_parent(me,1);
}
Node* access(Node *me)
{
Node *up=me;
splay(me);
detach_path(me);
while(me->pathp)
{
up=me->pathp;
me->pathp=nullptr;
splay(up);
detach_path(up);
make_parent(up,1,me);
splay(me);
}
return up;
}
void cut(Node *me)
{
// cout << "cut " << me->a << "_" << me->c << endl;
access(me);
unmake_parent(me,0);
}
void link(Node *me,Node *up)
{
// cout << "link [" << me->a << "_" << me->c << "," << up->a << "_" << up->c << "]" << endl;
access(me);
access(up);
make_parent(me,0,up);
}
int query(Node *me)
{
access(me);
return me->sum;
}
const int inf=2000000005;
int n,l;
vector<int> x;
vector<Node*> v;
set<array<int,3>> both; //x,col,id
set<array<int,3>> white;
array<int,3> rep(int a,int c)
{
return {(a!=0?(x[a]+c*l):(c*inf)),c,a};
}
Node* node(int a,int c)
{
if(a==0) return v[c==1];
else return v[2*a+c];
}
bool is_white(int a,int c)
{
return (a==0||c==1);
}
void add_set(int a,int c)
{
both.insert(rep(a,c));
if(is_white(a,c)) white.insert(rep(a,c));
}
void rm_set(int a,int c)
{
both.erase(rep(a,c));
if(is_white(a,c)) white.erase(rep(a,c));
}
array<int,2> prv_white(int a,int c)
{
auto it=white.lower_bound(rep(a,c));
it--;
return {(*it)[2],(*it)[1]};
}
array<int,2> nxt(int a,int c)
{
auto it=both.find(rep(a,c));
// assert(it!=both.end());
it++;
return {(*it)[2],(*it)[1]};
}
void connect(int a,int c)
{
auto it=both.upper_bound(rep(a,c));
link(node(a,c),node((*it)[2],(*it)[1]));
}
void add(int a)
{
add_set(a,0);
add_set(a,1);
// cout << "add " << a << endl;
// cout << "nxt: ";
// for(auto [x,y,z]:both) cout << "[" << x << "," << y << "," << z << "] ";
// cout << endl;
link(node(a,0),node(a,1));
auto [na,nc]=nxt(a,1);
link(node(a,1),node(na,nc));
// cout << "two" << endl;
auto [xa,xc]=prv_white(a,0);
auto [ya,yc]=prv_white(a,1);
bool diff=(xa!=ya||xc!=yc);
cut(node(xa,xc));
if(diff) cut(node(ya,yc));
connect(xa,xc);
if(diff) connect(ya,yc);
}
void rm(int a)
{
cut(node(a,1));
cut(node(a,0));
auto [xa,xc]=prv_white(a,0);
auto [ya,yc]=prv_white(a,1);
bool diff=(xa!=ya||xc!=yc);
cut(node(xa,xc));
if(diff) cut(node(ya,yc));
rm_set(a,0);
rm_set(a,1);
connect(xa,xc);
if(diff) connect(ya,yc);
}
void init(int nn,int nl,vector<int> nx)
{
n=nn;
l=nl;
x.assign(n+1,0);
for(int i=1;i<=n;i++) x[i]=nx[i-1];
v.assign(2*n+2,nullptr);
v[0]=new Node(0,-1,0);
v[1]=new Node(0,1,0);
for(int i=1;i<=n;i++)
{
v[2*i]=new Node(i,0,1);
v[2*i+1]=new Node(i,1,0);
}
link(v[0],v[1]);
add_set(0,-1);
add_set(0,1);
for(int i=1;i<=n;i++) add(i);
}
int update(int a,int y)
{
a++;
rm(a);
x[a]=y;
add(a);
return query(v[0]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// init(4,10,{10,15,17,20});
// cout << update(2,16) << endl;
// cout << update(1,25) << endl;
// cout << update(3,35) << endl;
// cout << update(0,38) << endl;
// cout << update(2,0) << endl;
return 0;
}