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;
}

Is Desk Productivity Tools...

📢 As an Amazon Associate, I earn from qualifying...

The Outer Worlds 2...

Gamers and RPG enthusiasts have reason to celebrate as...

Why Travel Organization Gear...

📢 As an Amazon Associate, I earn from qualifying...

Why Everyone Is Talking...

📢 As an Amazon Associate, I earn from qualifying...

Why Everyone Is Talking...

📢 As an Amazon Associate, I earn from qualifying...

Why Everyone Is Talking...

📢 As an Amazon Associate, I earn from qualifying...

Is Desk Productivity Tools Worth Your Money Here Is Our Full Review

📢 As an Amazon Associate, I earn from qualifying purchases.💰 Official Price: Check on Amazon🌟 Why Buy the Desk Productivity Tools?The Desk Productivity Tools...

The Outer Worlds 2 v1.2.0.1-TENOKE

Gamers and RPG enthusiasts have reason to celebrate as Obsidian Entertainment's acclaimed franchise returns with new developments. The highly anticipated sequel to the award-winning...

Why Travel Organization Gear Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.💰 Official Price: Check on Amazon🌟 Why Buy the Travel Organization Gear?The Travel Organization Gear...

Why Everyone Is Talking About the Car Detailing Essentials

📢 As an Amazon Associate, I earn from qualifying purchases.💰 Official Price: Check on Amazon🌟 Why Buy the Car Detailing Essentials?The Car Detailing Essentials...

Why Everyone Is Talking About the Smart Home Hacks

📢 As an Amazon Associate, I earn from qualifying purchases.💰 Official Price: Check on Amazon🌟 Why Buy the Smart Home Hacks?The Smart Home Hacks...

Why Everyone Is Talking About the Viral Kitchen Gadgets

📢 As an Amazon Associate, I earn from qualifying purchases.💰 Official Price: Check on Amazon🌟 Why Buy the Viral Kitchen Gadgets?The Viral Kitchen Gadgets...

Why Everyone Is Talking About the Travel Organization Gear

📢 As an Amazon Associate, I earn from qualifying purchases.💰 Official Price: Check on Amazon🌟 Why Buy the Travel Organization Gear?The Travel Organization Gear...

Why Everyone Is Talking About the Travel Organization Gear

📢 As an Amazon Associate, I earn from qualifying purchases.💰 Official Price: Check on Amazon🌟 Why Buy the Travel Organization Gear?The Travel Organization Gear...

GLP-1 Drugs Like Ozempic Carry Elevated Risks of Muscle Loss and Malnutrition in Adults Over 65

Understanding the Risks of GLP-1 Drugs for Older Adults GLP-1 receptor agonists, such as Ozempic, Wegovy, and Mounjaro, have transformed the landscape of weight management...