#include <bits/stdc++.h>
//#include "treasure.h"
using namespace std;
typedef long long ll;
const int N=2500000;
struct Node;
using twoNodes=array<Node*,2>;
struct Node
{
int val;
int l,r;
int sum;
int flip;
twoNodes kids;
Node *p;
Node *pathp;
twoNodes neighbours;
void ini(int a,int b){val=(b-a+1);l=a;r=b;sum=val;flip=0;kids[0]=kids[1]=p=pathp=nullptr;}
}buf[N];
int buf_now=0;
Node* newNode(int a,int b)
{
Node *t=&buf[buf_now++];
t->ini(a,b);
return t;
}
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 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);
}
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]=newNode(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(newNode(l,a-1));
v.push_back(newNode(a,a));
if(a<r) v.push_back(newNode(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=newNode(b,b);
auto it_pos=m.insert({b,e}).first;
split(a);
Node *node_a=find_node(a);
if(s==1) link(e,node_a);
else
{
Node *mid=newNode(id+1,b-1);
m.insert(it_pos,{id+1,mid});
mid->neighbours={node_a,e};
link(mid,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 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 |
1388 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1386 ms |
55336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2954 ms |
72428 KB |
Output is correct |
| 2 |
Correct |
1902 ms |
65724 KB |
Output is correct |
| 3 |
Correct |
1757 ms |
65920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1136 ms |
29676 KB |
Output is correct |
| 2 |
Correct |
1731 ms |
54548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3259 ms |
176908 KB |
Output is correct |
| 2 |
Correct |
2111 ms |
228516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1774 ms |
133744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3508 ms |
229668 KB |
Output is correct |
| 2 |
Correct |
486 ms |
107484 KB |
Output is correct |
| 3 |
Correct |
2646 ms |
126268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3078 ms |
245772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3043 ms |
245540 KB |
Output is correct |
