Submission #38854434

---

Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
using namespace std;
const int mod = 998244353;
void amod(int &x, int y) {
	x = x + y >= mod ? x + y - mod : x + y;
}
void dmod(int &x, int y) {
	x = x - y < 0 ? x - y + mod : x - y;
}
int inc(int x, int y) {
	return x + y >= mod ? x + y - mod : x + y;
}
const int maxn = 5e5 + 5;
int n, a[maxn], b[maxn], f[maxn], pw[maxn];
vector<int> upd[maxn];
int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	pw[0] = 1;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		pw[i] = 2ll * pw[i - 1] % mod;
	}
	for(int i = 1, l = 0, r = 0; i <= n; i++) {
		while(b[l] < a[i]) {
			l++;
		}
		while(r + 1 <= n && a[r + 1] < b[i]) {
			r++;
		}
		upd[r].eb(l);
	}
	f[0] = 1;
	for(int i = 1; i <= n; i++) {
		f[i] = inc(f[i - 1], f[i - 1]);
		for(int j : upd[i]) {
			dmod(f[i], f[j - 1]);
		}
	}
	cout << f[n] << '\n';
	return 0;
}

Submission Info

Judge Result