1586G - Omkar and Time Travel - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll Mod=1e9+7;
const int NN=4e5+5;
int n,a[NN],b[NN],t,s[NN];
int N;
ll v[NN*20];
int ls[NN*20],rs[NN*20],root[NN],tot;
void Update(int o1,int &o2,int l,int r,int p,int val){
	if(o2==0){
		tot++;
		o2=tot;
	}
	ls[o2]=ls[o1];
	rs[o2]=rs[o1];
	v[o2]=(v[o1]+val)%Mod;
	if(l==r){
		return ;
	}
	int mid=l+(r-l)/2;
	if(p<=mid){
		ls[o2]=0;
		Update(ls[o1],ls[o2],l,mid,p,val);
	}else{
		rs[o2]=0;
		Update(rs[o1],rs[o2],mid+1,r,p,val);
	}
}
ll Query(int o,int l,int r,int tl,int tr){
	if(tl<=l&&r<=tr){
//		cout<<l<<" "<<r<<" "<<v[o]<<'\n';
		return v[o];
	}
	if(o==0){
		return 0;
	}
	ll ret=0;
	int mid=l+(r-l)/2;
	if(tl<=mid){
		ret+=Query(ls[o],l,mid,tl,tr);
		ret%=Mod; 
	}
	if(mid<tr){
		ret+=Query(rs[o],mid+1,r,tl,tr);
		ret%=Mod;
	}
//	cout<<l<<" "<<r<<" "<<ret<<'\n';
	return ret;
}
bool cmp(const int&x,const int&y){
	return b[x]<b[y];
}
struct task{
	int a,b;
}ta[NN];
bool cmp2(const task&x,const task&y){
	return x.b<y.b;
}
ll ans;
void solve(int now){
	int nxt=now-1;
	while(a[s[nxt]]<a[s[now]]&&nxt>0){
		nxt--;
	}
	if(nxt==0){
		return ;
	}else{
		ans+=Query(root[b[s[nxt]]],1,N,a[s[now]]+1,b[s[nxt]])+1-Query(root[b[s[nxt]]],1,N,a[s[nxt]],a[s[nxt]]);
//		cout<<now<<":"<<a[s[now-1]]+1<<" "<<b[s[now]]<<" "s<<Query(root[s[now]],1,N,a[s[now-1]]+1,b[s[now]])<<'\n';
		ans=(ans%Mod+Mod)%Mod;
		solve(nxt);
	}
}
int main(){
//	freopen("ott.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	N=n*2;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		ta[i].a=a[i];
		ta[i].b=b[i];
	}
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>s[i];
	}
	sort(s+1,s+t+1,cmp);
	sort(ta+1,ta+n+1,cmp2);
	for(int i=1;i<=n;i++){
//		cout<<"at "<<ta[i].a<<" "<<ta[i].b<<'\n';
		if(ta[i].b==b[s[t]]){
			ans+=1;
			ans%=Mod;
//			cout<<"before solve "<<ans<<'\n';
			solve(t);
//			cout<<"after solve"<<ans<<'\n';
			break;
		}else{
			ll val=Query(root[ta[i-1].b],1,N,ta[i].a,ta[i].b-1);
//			cout<<val+1<<'\n';
			val=((val+1)%Mod+Mod)%Mod;
			ans=(ans+val)%Mod;
			Update(root[ta[i-1].b],root[ta[i].b],1,N,ta[i].a,val);
		} 
	}
	cout<<ans;
	return 0;
}