#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
//#include "treasure.h"
using namespace std;
typedef long long ll;
struct Node;
using twoNodes=array<Node*,2>;
struct Node
{
int val;
int l,r;
int sum;
int sz;
int flip;
twoNodes kids;
Node *p;
Node *pathp;
twoNodes neighbours;
Node(int a,int b){val=(b-a+1);l=a;r=b;sum=val;sz=1;flip=0;kids[0]=kids[1]=p=pathp=nullptr;}
};
int sz(Node *me){return (me?me->sz:0);}
int side(Node *me){return (me->p?(me->p->kids[1]==me):0);}
void recalc(Node *me)
{
if(!me) return;
me->sz=1;
me->sum=me->val;
for(Node *to:me->kids) if(to) {me->sz+=to->sz;me->sum+=to->sum;}
}
void apply(Node *me)
{
if(!me) return;
swap(me->kids[0],me->kids[1]);
me->flip^=1;
}
void prop(Node *me)
{
if(me&&me->flip==1)
{
for(Node *to:me->kids) apply(to);
me->flip=0;
}
}
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)
{
prop(me->p->p);
prop(me->p);
prop(me);
if(me->p->p)
{
if(side(me)==side(me->p)) rotate_up(me->p);
else rotate_up(me);
}
rotate_up(me);
}
prop(me);
recalc(me);
}
Node* find_kth(Node *me,int cnt)
{
prop(me);
if(sz(me->kids[0])>=cnt) return find_kth(me->kids[0],cnt);
else if(sz(me->kids[0])==cnt-1) return me;
else return find_kth(me->kids[1],cnt-sz(me->kids[0])-1);
}
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 make_root(Node *me)
{
access(me);
apply(me);
}
void cut(Node *me)
{
access(me);
unmake_parent(me,0);
}
void link(Node *me,Node *up)
{
access(me);
access(up);
make_parent(me,0,up);
}
map<int,Node*> m;
int id;
void init()
{
m[1]=new Node(1,1);
id=1;
}
map<int,Node*>::iterator find_it(int a)
{
auto it=m.lower_bound(a+1);
it--;
return it;
}
Node* find_node(int a)
{
return (find_it(a)->second);
}
void split(int a)
{
auto it=find_it(a);
Node *now=(it->second);
int l=now->l;
int r=now->r;
if(l==r) return;
Node *prv=(now->neighbours[0]);
Node *nxt=(now->neighbours[1]);
make_root(now);
cut(prv);
cut(nxt);
auto it_pos=m.erase(it);
vector<Node*> v={prv};
if(l<a) v.push_back(new Node(l,a-1));
v.push_back(new Node(a,a));
if(a<r) v.push_back(new Node(a+1,r));
v.push_back(nxt);
for(int i=1;i<(int)v.size()-1;i++) m.insert(it_pos,{v[i]->l,v[i]});
for(int i=0;i<(int)v.size()-1;i++)
{
make_root(v[i]);
link(v[i],v[i+1]);
if(i>0) v[i]->neighbours={v[i-1],v[i+1]};
}
}
void path(int a,int s)
{
int b=id+s;
Node *e=new Node(b,b);
auto it_pos=m.insert({b,e}).first;
split(a);
if(s==1) link(e,find_node(a));
else
{
Node *mid=new Node(id+1,b-1);
m.insert(it_pos,{id+1,mid});
mid->neighbours={find_node(a),e};
link(mid,find_node(a));
link(e,mid);
}
id=b;
// cout << "after op:" << endl;
// for(auto [x,p]:m)
// {
// cout << "[" << x[0] << "," << x[1] << "]: " << p << endl;
// }
}
void pr(Node *me)
{
if(!me) return;
prop(me);
pr(me->kids[0]);
cout << "[" << me->l << "," << me->r << "] ";
pr(me->kids[1]);
}
Node* descend(Node *me,int cnt)
{
prop(me);
int l=(me->kids[0]?me->kids[0]->sum:0);
if(l>=cnt) return descend(me->kids[0],cnt);
cnt-=l;
if(me->val>=cnt) return me;
cnt-=(me->val);
return descend(me->kids[1],cnt);
}
Node* find_prv(Node *me)
{
prop(me);
me=me->kids[0];
prop(me);
while(me->kids[1])
{
me=me->kids[1];
prop(me);
}
splay(me);
return me;
}
int dig(int a,int b)
{
split(a);
split(b);
Node *one=find_node(a);
Node *two=find_node(b);
make_root(one);
access(two);
splay(one);
// cout << "path a->b: ";
// pr(one);
// cout << endl;
int path_len=(one->sum);
int half_len=(path_len+1)/2;
// cout << "path_len=" << path_len << endl;
Node *t=descend(one,half_len);
splay(t);
if(t->val==1) return (t->l);
Node *prv=find_prv(t);
int src=(prv->l);
int here_len=(prv->val+(prv->kids[0]?prv->kids[0]->sum:0));
splay(t);
int kth=(half_len-here_len);
int c=t->l;
int d=t->r;
if(src<c) return c+kth-1;
else return d-kth+1;
// int l=0,r=num_nodes;
// while(l<r-1)
// {
// int mid=(l+r)/2;
// splay(one);
// Node* t=find_kth(one,mid);
// splay(t);
// int here_len=(t->val+(t->kids[0]?t->kids[0]->sum:0));
// if(here_len>=half_len) r=mid;
// else l=mid;
// }
//// cout << "r=" << r << endl;
// splay(one);
// Node *t=find_kth(one,r);
// if(t->val==1) return (t->l);
// else
// {
// splay(one);
// t=find_kth(one,r-1);
// splay(t);
// int src=(t->l);
// assert(t->val==1);
// int here_len=(t->val+(t->kids[0]?t->kids[0]->sum:0));
//// cout << "here_len=" << here_len << endl;
// splay(one);
// t=find_kth(one,r);
// splay(t);
// int kth=(half_len-here_len);
// int c=t->l;
// int d=t->r;
// if(src<c) return c+kth-1;
// else return d-kth+1;
// }
}
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// int n;
// cin >> n;
// while(n--)
// {
// char t;
// int a,b;
// cin >> t >> a >> b;
// if(t=='i') init();
// else if(t=='p') path(a,b);
// else if(t=='d') cout << dig(a,b) << endl;
// }
// return 0;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1472 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1470 ms |
58860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3184 ms |
77548 KB |
Output is correct |
| 2 |
Correct |
2123 ms |
70636 KB |
Output is correct |
| 3 |
Correct |
1878 ms |
70388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1148 ms |
31852 KB |
Output is correct |
| 2 |
Correct |
1880 ms |
58332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3643 ms |
189064 KB |
Output is correct |
| 2 |
Correct |
2358 ms |
242956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1954 ms |
141876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3765 ms |
244368 KB |
Output is correct |
| 2 |
Correct |
571 ms |
124908 KB |
Output is correct |
| 3 |
Correct |
2813 ms |
145908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3366 ms |
262144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3306 ms |
262144 KB |
Output is correct |
