tricky 题。
首先考虑把实数规避掉，由于 \(K\) 是整数，在时刻 \(10.1, 10.2, 10.3\) 出发都是等价的，我们可以只考虑从 \(10\) 出发，出发时播放的幻灯片可以被看到。也就是说 \(10\) 出发代表着 \(10 + \epsilon\) 出发而非真正的 \(10\) 出发。以此，我们将 \((l, r)\) 转化为了 \([l, r - 1]\)，因为只有整数了。
考虑 DP，时间放状态里肯定不行，我们考虑 \(dp_{i, j=0/1, k=0/1}\) 表示当前看了 \(i\) 张，现在在教室 \(j\)，如果当前立马冲到另一个教室，所看到的幻灯片是否在之前已经被看过。这是为了方便转移。
转移就是考虑现在要不要过去。另外由于可能冲过去发现是看过的幻灯片，于是 \(i\) 不会增加，也就是说可能会从 \(i\) 转移到 \(i\)，正常这种问题需要跑最短路，但是这里由于最多多转移一次，所以转移两次即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。常数还是比较大的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 3e5 + 10, inf = 0x3f3f3f3f;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n[2], m, dp[N << 1][2][2], ans;
struct Seg {int l, r;bool operator < (const Seg &A) const {return l < A.l;}bool operator < (const int &A) const {return r < A;}
} a[2][N];
int get(int typ, int x) { return lower_bound(a[typ] + 1, a[typ] + n[typ] + 1, x) - a[typ]; }
int find(int typ, int x) {int cur = get(typ, x);return a[typ][cur].l <= x ? cur : 0;
}
int next(int typ, int x) {int cur = get(typ, x);return cur + (a[typ][cur].l <= x);
}
void cmin(int &x, int y) { if (x > y) x = y; }
void main() {cin >> n[0] >> n[1] >> m;n[0]++; n[1]++; a[0][n[0]] = a[1][n[1]] = {inf, inf};for (int i = 1; i < n[0]; i++) cin >> a[0][i].l >> a[0][i].r, a[0][i].r--;for (int i = 1; i < n[1]; i++) cin >> a[1][i].l >> a[1][i].r, a[1][i].r--;sort(a[0] + 1, a[0] + n[0] + 1); sort(a[1] + 1, a[1] + n[1] + 1);memset(dp, 0x3f, sizeof dp);dp[!a[0][1].l][0][0] = 0;for (int i = !a[0][1].l; i <= n[0] + n[1]; i++) {for (int turn = 0; turn < 2; turn++) {for (int j = 0; j < 2; j++) {for (int k = 0; k < 2; k++) if (dp[i][j][k] < inf) {int t = dp[i][j][k], now = find(j, t), to = find(j ^ 1, t + m), nxt = next(j, t);cmin(dp[i + (to && !k)][j ^ 1][now && find(j, t + 2 * m) == now], t + m);cmin(dp[i + 1][j][to && k && find(j ^ 1, a[j][nxt].l + m) == to], a[j][nxt].l);ans = i;}}}}cout << ans << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}
// start coding at 20:16
// finish debugging at 20:33