Submission #71518506

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace IO {
	template<typename T> inline void read(T &x) {
		bool f = 1;
		x = 0;
		char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-')f = 0;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
		x = f ? x : -x;
	}
	template<typename T> inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(('0' + x % 10));
	}
	template <typename T, typename ...Args> inline
	void read(T &x, Args &...args) {
		read(x), read(args...);
	}
	template<typename T> inline void write(T x, char c) {
		write(x), putchar(c);
	}
}
using namespace IO;
const int INF = 1e18;
const int MOD = 998244353;

inline int addmod(int a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
	return a;
}
inline int submod(int a, int b) {
	a -= b;
	if (a < 0) a += MOD;
	return a;
}
inline int mulmod(int a, int b) {
	return (a * b) % MOD;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, M;
	cin >> N >> M;
	int E = max(0ll, N - 1);
	vector<int> L(M + 1), R(M + 1);
	for (int i = 1; i <= M; i++) cin >> L[i] >> R[i];

	vector<int> diff(E + 3, 0);
	for (int c = 1; c <= M; c++) {
		if (L[c] <= R[c] - 1) {
			diff[L[c]]++;
			if (R[c] <= E) diff[R[c]]--;
		}
	}
	vector<int> w(E + 2, 0);
	int cur = 0;
	for (int i = 1; i <= E; i++) {
		cur += diff[i];
		w[i] = cur % MOD;
	}

	vector<vector<int>> st(E + 3), fil(E + 3);
	for (int c = 1; c <= M; c++) {
		if (L[c] <= R[c] - 1) {
			st[L[c]].push_back(c);
			if (R[c] <= E) fil[R[c]].push_back(c);
		}
	}

	vector<int> ops0, ops1;
	vector<int> alt0(1, 0), alt1(1, 0);

	auto push_op = [&](int parity, int A) {
		if (parity == 0) {
			int idx = (int)ops0.size();
			ops0.push_back(A);
			int add = (idx % 2 == 0) ? A : submod(0, A);
			alt0.push_back(addmod(alt0.back(), add));
		} else {
			int idx = (int)ops1.size();
			ops1.push_back(A);
			int add = (idx % 2 == 0) ? A : submod(0, A);
			alt1.push_back(addmod(alt1.back(), add));
		}
	};

	auto calc_segment_l = [&](int parity, int a, int b)->int{
		int k = b - a;
		if (k == 0) return 0;
		int diff = 0;
		if (parity == 0) diff = submod(alt0[b], alt0[a]);
		else diff = submod(alt1[b], alt1[a]);
		int mult = (( (b - 1) % 2 ) == 0) ? 1 : (MOD - 1);
		return mulmod(mult, diff);
	};

	vector<int> start0(M + 1, 0), start1(M + 1, 0);
	vector<char> active(M + 1, 0);

	int ans1 = 1, ans2 = 1;
	int cnt_active = 0;
	int sumL0 = 0, sumL1 = 0;

	for (int i = 1; i <= E; i++) {
		for (int c : st[i]) {
			if (!active[c]) {
				active[c] = 1;
				start0[c] = (int)ops0.size();
				start1[c] = (int)ops1.size();
				cnt_active++;
			}
		}
		for (int c : fil[i]) {
			if (active[c]) {
				int end0 = (int)ops0.size();
				int end1 = (int)ops1.size();
				int l0c = calc_segment_l(0, start0[c], end0);
				int l1c = calc_segment_l(1, start1[c], end1);
				sumL0 = submod(sumL0, l0c);
				sumL1 = submod(sumL1, l1c);
				active[c] = 0;
				cnt_active--;
			}
		}

		int p = i % 2;
		int sum = (p == 0 ? sumL0 : sumL1);

		int x = addmod(ans1, mulmod(ans2, w[i]));
		x = submod(x, sum);

		if (p == 0) {
			int tmp = mulmod(cnt_active % MOD, ans2);
			sumL0 = submod(tmp, sumL0);
		} else {
			int tmp = mulmod(cnt_active % MOD, ans2);
			sumL1 = submod(tmp, sumL1);
		}

		push_op(p, ans2);

		ans2 = ans1;
		ans1 = x;
	}

	cout << ( (ans1 % MOD + MOD) % MOD ) << "\n";
	return 0;
}

Submission Info

Judge Result