Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2), problem: (F) Beautiful fountains rows Solution In C/C++

include<cstdio>
using namespace std;
inline int read(){
	char c=getchar();int p=1,ret=0;
	while((c<'0')||(c>'9')){if(c=='-')p=-1;c=getchar();}
	while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ret*p;
}
int n,m;
long long ans;
struct tree{
	int v[2][2],num[2][2];
	long long sum[2][2];
	void add(int x,int y,int p){v[x][y]+=p;}
}t[1600005];
struct ele{
	int l,r;
}e[200005];
int head[200005],Head[200005],nex[200005],Nex[200005];
int sum[200005];
#define mid ((l+r)>>1)
#define lson index<<1
#define rson index<<1|1
inline bool cmp(ele k1,ele k2){return k1.l<k2.l;}
inline bool Cmp(ele k1,ele k2){return k1.r<k2.r;}
void pushup(int index,int i,int j){
	t[index].num[i][j]=t[index].sum[i][j]=0;
	if(t[lson].v[i][j]==0){
		t[index].num[i][j]+=t[lson].num[i][j];
		t[index].sum[i][j]+=t[lson].sum[i][j];
	}
	if(t[rson].v[i][j]==0){
		t[index].num[i][j]+=t[rson].num[i][j];
		t[index].sum[i][j]+=t[rson].sum[i][j];
	}
}
void build(int l,int r,int index){
	if(l==r){
		t[index].num[0][r&1]=1;t[index].sum[0][r&1]=r;
		t[index].num[1][r&1]=1;t[index].sum[1][r&1]=r;
		return;
	}
	build(l,mid,lson);build(mid+1,r,rson);
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)pushup(index,i,j);
}
void add(int l,int r,int L,int R,int x,int y,int v,int index){
//	if((l==1)&&(r==n))printf("%d %d %d %d %d\n",L,R,x,y,v);
	if((L<=l)&&(R>=r)){t[index].add(x,y,v);return;}
	if(L<=mid)add(l,mid,L,R,x,y,v,lson);
	if(R>mid)add(mid+1,r,L,R,x,y,v,rson);
	pushup(index,x,y);
}
void workl(int l,int r){
	add(1,n,l,r,0,l&1^1,-1,1);
	add(1,n,l,r,1,l&1^1,-1,1);
	if(((r-l)&1)&&(r<n)){
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)add(1,n,r+1,n,j,k,-1,1);
	}
	for(int i=0;i<2;i++){
		add(1,n,l,r,i,i^1,1,1);
		if(r<n)add(1,n,r+1,n,r&1^1,i,1,1);
	}
}
void workr(int l,int r){
	for(int i=0;i<2;i++){
		add(1,n,l,r,i,i^1,-1,1);
		if(r<n)add(1,n,r+1,n,r&1^1,i,-1,1);
	}
}
int x[2][2];
void query(int l,int r,int k,int index){
	if(l>=k){
		for(int i=0;i<2;i++)if(x[k&1][i]+t[index].v[k&1][i]==0)ans+=t[index].sum[k&1][i]-1LL*t[index].num[k&1][i]*(k-1);
		return;
	}
	for(int i=0;i<2;i++)x[k&1][i]+=t[index].v[k&1][i];
	if(k<=mid)query(l,mid,k,lson);
	query(mid+1,r,k,rson);
	for(int i=0;i<2;i++)x[k&1][i]-=t[index].v[k&1][i];
}
int main(){
	m=read();n=read();
	build(1,n,1);
	for(int i=1;i<=m;i++){
		e[i].l=read(),e[i].r=read();
		nex[i]=head[e[i].l];Nex[i]=Head[e[i].r];
		head[e[i].l]=i;Head[e[i].r]=i;
	}
	for(int i=1;i<=m;i++){
		add(1,n,e[i].l,e[i].r,0,e[i].l&1^1,1,1);
		add(1,n,e[i].l,e[i].r,1,e[i].l&1^1,1,1);
		if(((e[i].r-e[i].l)&1)&&(e[i].r<n)){
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)add(1,n,e[i].r+1,n,j,k,1,1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nex[j])workl(e[j].l,e[j].r);
		for(int j=Head[i-1];j;j=Nex[j])workr(e[j].l,e[j].r);
		query(1,n,i,1);
	}
	for(int i=1;i<=m;i++)sum[e[i].l]++,sum[e[i].r+1]--;
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	int last=0;
	for(int i=1;i<=n;i++)if(sum[i]==0)last++,ans-=1LL*last*(last+1)/2;
	else last=0;
	printf("%I64d",ans);
}