分析

容易发现时间不好离散化，考虑作为状态处理。

首先让所有的时间乘上 $10^4$，然后再让所有 PPT 放映时间右端点减去 $1$ 即可，那么这个时候只要我们在一瞬间（可以无限短）看到了 PPT 就算看到了，而非题目中的停留正数时间。

于是设 $f_{i,j,k}$ 表示当前看了 $i$ 个 PPT 并且在第 $j$ 个教室，另外一个教室在 $f_{i,j,k}$ 这个时刻放映的 PPT 看没看过（$k=0,1$）最少用时为 $f_{i,j,k}$。

转移只有两种：

• 待在当前教室等到当前教室的下一张 PPT。

• 花费 $K$ 的时间走到另外的一个教室。

转移比较简单，这里详细叙述一下第一种转移：

设 $t$ 为当前教室下一堂课的开始时间。

首先 $i$ 一定会加一，因为 $f_{i,j,k}$ 这个时刻之前一定没有看过这个教室的下一张 PPT；$j$ 不变，显然；如果 $k=0$，那么 $k$ 不变，如果 $k=1$ 并且另外一个教室在 $f_{i,j,k}$ 时刻放映的 PPT 与在 $t$ 时刻放映的 PPT 相同，那么 $k=1$，否则 $k=0$。

转移即为 $f_{i',j',k'} \gets \min(f_{i',j',k'},t)$。

另外一个转移同理。

注意到有可能循环转移，但是转移的时候值只会越来越大，所以直接转移两遍，或者从最小值开始转移即可。

我们需要知道一个教室在任意时刻放映的 PPT 是什么，这个可以二分解决，于是时间复杂度就是 $O(n \log n)$。

代码

代码如下，仅供参考：

#include<bits/stdc++.h>
#define ll long long
#define N 600005
using namespace std;
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0;
	char c = nc();
	while(c<'0'||c>'9')c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res;
}
char obuf[1<<21],*p33=obuf; 
inline void pc(char c){ 
	p33-obuf<=(1<<20)?(*p33++=c):(fwrite(obuf,p33-obuf,1,stdout),p33=obuf,*p33++=c); 
} 
inline void write(ll x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
struct node{ll x,y;}p1[N],p2[N];
inline bool cmp(node a,node b){return a.x<b.x;}
ll n1,n2,lenth,i,j,k,f[N][2][2];
inline ll found_cover(ll id,ll x){
	if(id==0){
		ll l=1,r=n1;
		while(l<r){
			ll mid = (l+r+1)/2;
			if(p1[mid].x<=x) l=mid;
			else r=mid-1;
		}
		if(p1[l].x<=x&&x<=p1[l].y) return l;
		else return 0;
	}
	else{
		ll l=1,r=n2;
		while(l<r){
			ll mid = (l+r+1)/2;
			if(p2[mid].x<=x) l=mid;
			else r=mid-1;
		}
		if(p2[l].x<=x&&x<=p2[l].y) return l;
		else return 0;
	}
}
inline ll found_next(ll id,ll x){
	if(id==0){
		ll l=0,r=n1;
		while(l<r){
			ll mid = (l+r+1)/2;
			if(p1[mid].x<=x) l=mid;
			else r=mid-1;
		}
		return l+1;
	}
	else{
		ll l=0,r=n2;
		while(l<r){
			ll mid = (l+r+1)/2;
			if(p2[mid].x<=x) l=mid;
			else r=mid-1;
		}
		return l+1;
	}
}
ll base = 1;
int main(){
	memset(f,0x3f,sizeof(f));
//	freopen("2.in","r",stdin);
	n1=read(),n2=read(),lenth=read(),lenth*=base;
	for(i=1;i<=n1;i++) p1[i].x=read(),p1[i].y=read(),p1[i].x=p1[i].x*base,p1[i].y=p1[i].y*base-1;
	for(i=1;i<=n2;i++) p2[i].x=read(),p2[i].y=read(),p2[i].x=p2[i].x*base,p2[i].y=p2[i].y*base-1;
	sort(p1+1,p1+n1+1,cmp),sort(p2+1,p2+n2+1,cmp);
	f[(p1[1].x==0)][0][0] = 0;
	for(i=0;i<=n1+n2;i++){
		for(j=0;j<2;j++){
			for(k=0;k<2;k++){
				if(f[i][j][k]>1e18) continue;
				//stay here until the next class
				ll pos = found_next(j,f[i][j][k]),t1,t2;
				if(pos>(j==0?n1:n2)) goto end1;
				t1 = found_cover(j^1,f[i][j][k]),t2 = found_cover(j^1,(j==0?p1[pos].x:p2[pos].x));
				f[i+1][j][k&&(t1==t2)] = min(f[i+1][j][k&&(t1==t2)],(j==0?p1[pos].x:p2[pos].x));
				end1:;
				//change the class with lenth minutes' walk
				ll c1 = found_cover(j^1,f[i][j][k]),c2 = found_cover(j^1,f[i][j][k]+lenth),c3 = found_cover(j,f[i][j][k]),c4 = found_cover(j,f[i][j][k]+lenth);
				f[i+(!(k&&c1==c2)&&c2!=0)][j^1][c3==c4&&c3!=0] = min(f[i+(!(k&&c1==c2)&&c2!=0)][j^1][c3==c4&&c3!=0],f[i][j][k]+lenth);
			}
		}
		for(j=0;j<2;j++){
			for(k=0;k<2;k++){
				if(f[i][j][k]>1e18) continue;
				//stay here until the next class
				ll pos = found_next(j,f[i][j][k]),t1,t2;
				if(pos>(j==0?n1:n2)) goto end2;
				t1 = found_cover(j^1,f[i][j][k]),t2 = found_cover(j^1,(j==0?p1[pos].x:p2[pos].x));
				f[i+1][j][k&&(t1==t2)] = min(f[i+1][j][k&&(t1==t2)],(j==0?p1[pos].x:p2[pos].x));
				end2:;
				//change the class with lenth minutes' walk
				ll c1 = found_cover(j^1,f[i][j][k]),c2 = found_cover(j^1,f[i][j][k]+lenth),c3 = found_cover(j,f[i][j][k]),c4 = found_cover(j,f[i][j][k]+lenth);
				f[i+(!(k&&c1==c2)&&c2!=0)][j^1][c3==c4&&c3!=0] = min(f[i+(!(k&&c1==c2)&&c2!=0)][j^1][c3==c4&&c3!=0],f[i][j][k]+lenth);
			}
		}
//		cout<<f[i][0][0]<<" "<<f[i][0][1]<<" "<<f[i][1][0]<<" "<<f[i][1][1]<<endl;
	}
	for(i=n1+n2;i>=0;i--){
		if(min({f[i][0][0],f[i][0][1],f[i][1][0],f[i][1][1]})<=1e18){
			write(i);
			break;
		}
	}
	return fwrite(obuf,p33-obuf,1,stdout),0;
}