QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333248#6673. Be Careful 2ucup-team1198#WA 1ms3788kbC++175.9kb2024-02-19 19:11:002024-02-19 19:11:01

Judging History

你现在查看的是最新测评结果

  • [2024-02-19 19:11:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3788kb
  • [2024-02-19 19:11:00]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MOD = 998244353;

int add(int a, int b) {
	if (a + b < MOD)
		return a + b;
	return a + b - MOD;
}

int sub(int a, int b) {
	if (a >= b)
		return a - b;
	return a + MOD - b;
}

int mul(int a, int b) {
	return a * 1ll * b % MOD;
}

int pw(int a, int n) {
	int ans = 1;
	while (n) {
		if (n & 1)
			ans = mul(ans, a);
		n >>= 1;
		a = mul(a, a);
	}
	return ans;
}

int get0(int l) {
	return l % MOD;
}

int get1(int l) {
	return ((1ll * l * (l - 1)) / 2) % MOD;
}

int get2(int l) {
	int64_t res = (1ll * l * (l - 1)) / 2;
	if (res % 3 == 0) {
		res /= 3;
		res %= MOD;
		return (1ll * res * (2 * l - 1)) % MOD;
	} else {
		res %= MOD;
		return ((1ll * res * (2 * l - 1)) / 3) % MOD;
	}
}

int get3(int l) {
	return mul(get1(l), get1(l));
}

const int F = pw(5, MOD - 2);

int get4(int l) {
	int ans = mul(l, mul(l - 1, mul(l - 2, mul(l - 3, l - 4))));
	ans = mul(ans, F);
	return add(ans, sub(mul(6, get3(l)), sub(mul(11, get2(l)), mul(6, get1(l)))));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
		
	int n, m, k;
	cin >> n >> m >> k;

	auto get_seg = [](int mn, int mx, int n) {
		/// d >= 0
		vector<pair<array<int, 2>, vector<int>>> ans; /// {{l, r}, P(d)}, for d in [l, r) ans is P(d)
		/// min(mn, n - mx, n - d, d - mx + mn)
		/// it's mn:
		{
			int l = 0, r = n;
			if (mn <= 0) l = n;
			if (mn >= n - mx) {
				l = n;
			}
			r = min(r, n - mn);
			l = max(l, mx + 1);
			if (l < r) {
				vector<int> p = {mn, 0};
				ans.push_back({{l, r}, p});
			}
		}
		/// it's n - mx:
		{
			int l = 0, r = n;
			if (n - mx <= 0) l = n;
			if (n - mx > mn) {
				l = n;
			}
			r = min(r, mx);
			l = max(l, n - mn + 1);
			if (l < r) {
				vector<int> p = {n - mx, 0};
				ans.push_back({{l, r}, p});
			}
		}
		/// it's n - d:
		{
			int l = 0, r = n;
			l = max(l, n - mn);
			l = max(l, mx);
			l = max(l, (n + mx - mn) / 2 + 1);
			if (l < r) {
				vector<int> p = {n + 1, -1};
				ans.push_back({{l, r}, p});
			}
		}
		/// it's d - mx + mn:
		{
			int l = 0, r = n;
			r = min(r, mx + 1);
			r = min(r, n - mn + 1);
			r = min(r, (n + mx - mn) / 2 + 1);
			l = max(l, mx - mn + 1);
			if (l < r) {
				vector<int> p = {-mx + mn - 1, 1};
				ans.push_back({{l, r}, p});
			}
		}
		for (int i = 0; i < (int)ans.size(); ++i) {
			for (int& x : ans[i].second) {
				x %= MOD;
				if (x < 0) x += MOD;
			}
		}
		return ans;
	};

	auto get_cnt = [&](int mnx, int mxx, int mny, int mxy) {
		auto ansx = get_seg(mnx, mxx, n);
		auto ansy = get_seg(mny, mxy, m);
		int sum = 0;
		for (auto ex : ansx) {
			for (auto ey : ansy) {
				int l = max(ex.first[0], ey.first[0]);
				int r = min(ex.first[1], ey.first[1]);
				if (l >= r) continue;
				int p0 = mul(ex.second[0], ey.second[0]);
				int p1 = add(mul(ex.second[0], ey.second[1]), 
							 mul(ex.second[1], ey.second[0]));
				int p2 = mul(ex.second[1], ey.second[1]);
				/// bool f = (sum == 0);
				sum = add(sum, mul(p0, sub(get2(r + 1), get2(l + 1))));
				sum = add(sum, mul(p1, sub(get3(r + 1), get3(l + 1))));
				sum = add(sum, mul(p2, sub(get4(r + 1), get4(l + 1))));
				/**f &= (sum != 0);
				if (f) {
					cout << l << " " << r << " " << ex.second[0] << " " << ex.second[1] << " " << ey.second[0] << " " << ey.second[1] << endl;
				}*/
			}
		}

		/**int check = 0;
		for (int d = 1; d <= n; ++d) {
			int x = min(mnx, min(n - mxx, min(n - d + 1, d - 1 - mxx + mnx)));
			int y = min(mny, min(m - mxy, min(m - d + 1, d - 1 - mxy + mny)));
			if (x <= 0 || y <= 0) continue;
			check += x * y;
		}
		assert(check == sum);*/

		return sum;
	};

	/**for (int mnx = 0; mnx <= n; ++mnx) {
		for (int mxx = mnx; mxx <= n; ++mxx) {
			for (int mny = 0; mny <= m; ++mny) {
				for (int mxy = mny; mxy <= m; ++mxy) {
					get_cnt(mnx, mxx, mny, mxy);
				}
			}
		}
	}*/

	vector<array<int, 2>> arr(k);
	for (int i = 0; i < k; ++i) {
		cin >> arr[i][0] >> arr[i][1];
	}
	int ans = 0;
	
	auto apply = [&](vector<int> ind) {
		sort(ind.begin(), ind.end());
		int k = unique(ind.begin(), ind.end()) - ind.begin();
		int mnx = n + 1, mxx = -1, mny = m + 1, mxy = -1;
		for (int i : ind) {
			mnx = min(mnx, arr[i][0]);
			mxx = max(mxx, arr[i][0]);
			mny = min(mny, arr[i][1]);
			mxy = max(mxy, arr[i][1]);
		}
		/// cerr << mnx << " " << mxx << " " << mny << " " << mxy << endl;
		int res = get_cnt(mnx, mxx, mny, mxy);
		if (k % 2 == 1) res = sub(0, res);
		ans = add(ans, res);
	};

	apply({});

	/// cerr << ans << endl;

	vector<int> ordx(k), ordy(k);
	iota(ordx.begin(), ordx.end(), 0);
	iota(ordy.begin(), ordy.end(), 0);

	auto cmpx = [&](int i, int j) { return arr[i][0] < arr[j][0]; };
	auto cmpy = [&](int i, int j) { return arr[i][1] < arr[j][1]; };
	sort(ordx.begin(), ordx.end(), cmpx);
	sort(ordy.begin(), ordy.end(), cmpy);

	vector<int> y1(n);
	for (int i = 0; i < n; ++i) {
		y1[ordy[i]] = i;
	}
	auto cmp = [&](int i, int j) { return y1[i] < y1[j]; };
	auto get_min = [&](int i, int j) { return cmp(i, j) ? i : j; };

	for (int li = 0; li < k; ++li) {
		int l = ordx[li];
		/// l == r:
		apply({l});
		set<int, decltype(cmp)> st(cmp);
		st.insert(l);
		for (int ri = li + 1; ri < k; ++ri) {
			int r = ordx[ri];
			st.insert(r);
			int u = *st.upper_bound(get_min(l, r));
			auto it = st.lower_bound(l ^ r ^ get_min(l, r));
			--it;
			int d = *it;
			if (cmp(l, d) || cmp(r, d) || cmp(u, l) || cmp(u, r)) continue;
			/// cerr << l << " " << r << " " << u << " " << d << endl;
			apply({l, r, u, d});
		}
	}

	cout << ans << "\n";

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

3 3 1
2 2

output:

21

result:

ok 1 number(s): "21"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

5 5 2
2 1
2 4

output:

126

result:

ok 1 number(s): "126"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3756kb

input:

6 6 5
4 1
3 2
2 4
1 5
5 3

output:

446

result:

wrong answer 1st numbers differ - expected: '161', found: '446'