Codeforces Round #415 (Div. 1), problem: (D) Hitchhiking in the Baltic States Solution In C/C++

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define nMax 300010
#define INF 2000000100
using namespace std;
int n;
struct Node
{
int v,siz,add;
Node *son[2];
Node(){v=INF; siz=1; son[0]=son[1]=NULL; add=0;}
void update()
{
siz=1;
if(son[0]!=NULL) siz+=son[0]->siz;
if(son[1]!=NULL) siz+=son[1]->siz;
}
void add_add(int a)
{
add+=a; v+=a;
}
void push_down()
{
if(son[0]!=NULL) son[0]->add_add(add);
if(son[1]!=NULL) son[1]->add_add(add);
add=0;
}
}*ll[20];
Node *merge(Node *a,Node *b)
{
if(a==NULL) return b;
if(b==NULL) return a;
if((rand()%2))
{
a->push_down();
a->son[1]=merge(a->son[1],b);
a->update();
return a;
} else
{
b->push_down();
b->son[0]=merge(a,b->son[0]);
b->update();
return b;
}
}
void split(Node *r,int k,Node *&L,Node *&R)
{
if(k==0) {L=NULL; R=r; return;}
if(k==r->siz) {L=r; R=NULL; return;}
r->push_down();
int lsiz=0;
if(r->son[0]!=NULL) lsiz=r->son[0]->siz;
if(lsiz>=k)
{
split(r->son[0],k,L,R); r->son[0]=NULL; r->update();
R=merge(R,r);
} else
{
split(r->son[1],k-lsiz-1,L,R); r->son[1]=NULL; r->update();
L=merge(r,L);
}
}
Node *root;
int find(Node *r,int k)
{
if(r==NULL) return 0;
r->push_down();
if(r->v>k) return find(r->son[0],k);
int cnt=1;
if(r->son[0]!=NULL) cnt+=r->son[0]->siz;
return cnt+find(r->son[1],k);
}
Node *l1,*l2,*l3,*l4;
int main()
{
scanf(“%d”,&n);
root=new Node;
root->v=0;
for(int i=1;i<=n;i++) root=merge(root,new Node());
for(int i=1;i<=n;i++)
{
int a,b;
scanf(“%d%d”,&a,&b);
int la=find(root,b-1);
split(root,la+1,l1,l4); split(l1,l1->siz-1,l1,l2);
la=find(l1,a-1);
split(l1,la,l1,l3);
l2->v=a;
if(l3!=NULL) l3->add_add(1);
root=merge(merge(l1,l2),merge(l3,l4));
}
printf(“%d\n”,find(root,2000000000)-1);
return 0;
}

SoftBank’s OpenAI bet and...

SoftBank Group Corp. has long been known for its...

Zydus Semaglutide approval: Delhi...

The Delhi High Court has stepped into a significant...

Why Everyone is Obsessed with the Electronics Cleaning Kit

Are you tired of dealing with everyday frustrations that slow down your routine? We've all been...

Why Everyone is Obsessed with the Desk LED Ring Light

Are you tired of dealing with everyday frustrations that slow down your routine? We've all been...

SoftBank’s OpenAI bet and rising debt are raising liquidity crunch concerns

SoftBank Group Corp. has long been known for its high-stakes, high-reward investment strategies under the leadership of Masayoshi Son. Recently, the conglomerate's aggressive pivot...

Why Everyone is Obsessed with the Herb Scissors 5 Blade

Are you tired of dealing with everyday frustrations that slow down your routine? We've all been...

Why Everyone is Obsessed with the Cable Management Box

Are you tired of dealing with everyday frustrations that slow down your routine? We've all been...

Zydus Semaglutide approval: Delhi HC directs CDSCO to decide on patient safety concerns

The Delhi High Court has stepped into a significant pharmaceutical regulatory matter by directing the Central Drugs Standard Control Organisation (CDSCO) to address patient...

Why Everyone is Obsessed with the Shower Phone Holder Case

Are you tired of dealing with everyday frustrations that slow down your routine? We've all been...

Why Everyone is Obsessed with the Universal Travel Adapter

Are you tired of dealing with everyday frustrations that slow down your routine? We've all been...

Why Everyone is Obsessed with the Bamboo Cutting Board Set

Are you tired of dealing with everyday frustrations that slow down your routine? We've all been...