QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333248 | #6673. Be Careful 2 | ucup-team1198# | WA | 1ms | 3788kb | C++17 | 5.9kb | 2024-02-19 19:11:00 | 2024-02-19 19:11:01 |
Judging History
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'