QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#182702 | #6673. Be Careful 2 | ucup-team004 | TL | 7948ms | 3972kb | C++20 | 10.4kb | 2023-09-18 14:11:30 | 2023-09-18 14:11:31 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MLong {
i64 x;
constexpr MLong() : x{} {}
constexpr MLong(i64 x) : x{norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
explicit constexpr operator i64() const {
return x;
}
constexpr MLong operator-() const {
MLong res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MLong &operator*=(MLong rhs) & {
x = mul(x, rhs.x, getMod());
return *this;
}
constexpr MLong &operator+=(MLong rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong &operator-=(MLong rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong &operator/=(MLong rhs) & {
return *this *= rhs.inv();
}
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
i64 v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};
template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 998244353;
using Z = MInt<P>;
struct Comb {
int n;
std::vector<Z> _fac;
std::vector<Z> _invfac;
std::vector<Z> _inv;
Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
Comb(int n) : Comb() {
init(n);
}
void init(int m) {
m = std::min(m, Z::getMod() - 1);
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
n = m;
}
Z fac(int m) {
if (m > n) init(2 * m);
return _fac[m];
}
Z invfac(int m) {
if (m > n) init(2 * m);
return _invfac[m];
}
Z inv(int m) {
if (m > n) init(2 * m);
return _inv[m];
}
Z binom(int n, int m) {
if (n < m || m < 0) return 0;
return fac(n) * invfac(m) * invfac(n - m);
}
} comb;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k;
std::cin >> n >> m >> k;
std::vector<int> x(k), y(k);
for (int i = 0; i < k; i++) {
std::cin >> x[i] >> y[i];
if (n > m) {
std::swap(x[i], y[i]);
}
}
if (n > m) {
std::swap(n, m);
}
std::vector<int> px(k), py(k);
std::iota(px.begin(), px.end(), 0);
std::sort(px.begin(), px.end(),
[&](int i, int j) {
return x[i] < x[j];
});
std::iota(py.begin(), py.end(), 0);
std::sort(py.begin(), py.end(),
[&](int i, int j) {
return y[i] < y[j];
});
std::vector<int> qx(k), qy(k);
for (int i = 0; i < k; i++) {
qx[px[i]] = i;
qy[py[i]] = i;
}
Z ans = Z(n) * (1 + n) * (2 + n) * (Z(-4) + n + Z(3) * n * n - Z(5) * m * (1 + n)) / -60;
auto get = [&](int x1, int y1, int x2, int y2) {
Z res = 0;
int bx = std::min(x1, n - x2);
int dx = x2 - x1 + 1;
int by = std::min(y1, m - y2);
int dy = y2 - y1 + 1;
int L = std::max(dx + 1, dy + 1);
int R = std::min(n, m);
if (L > R) {
return res;
}
std::vector<int> s{L, R};
s.push_back(bx + dx);
s.push_back(n + 1 - bx);
s.push_back((n + 1 + dx) / 2);
s.push_back((n + 1 + dx) / 2 + 1);
s.push_back(by + dy);
s.push_back(m + 1 - by);
s.push_back((m + 1 + dy) / 2);
s.push_back((m + 1 + dy) / 2 + 1);
std::sort(s.begin(), s.end());
auto get = [&](int d) {
return Z(d) * d * std::max(0, std::min({bx, d - dx, n + 1 - d}))
* std::max(0, std::min({by, d - dy, m + 1 - d}));
};
for (int i = 0; i < s.size() - 1; i++) {
int l = s[i], r = s[i + 1];
if (l == r || r <= L || l >= R) {
continue;
}
// if (r - l < 5) {
// for (int x = l; x < r; x++) {
// res += get(x);
// }
// continue;
// }
std::array<Z, 6> f;
f[0] = 0;
for (int j = 0; j < 5; j++) {
f[j + 1] = f[j] + get(l + j);
}
for (int x = 0; x <= 5; x++) {
Z v = 1;
for (int y = 0; y <= 5; y++) {
if (y != x) {
v = v * (r - l - y) / (x - y);
}
}
res += v * f[x];
}
}
res += get(R);
return res;
};
for (int i = 0; i < k; i++) {
ans -= get(x[i], y[i], x[i], y[i]);
}
for (int i = 0; i < k; i++) {
std::vector<int> l(k, -1), r(k, -1);
int lst = -1;
for (int j = 0; j < k; j++) {
if (qx[py[j]] >= i) {
if (lst != -1) {
l[py[j]] = lst;
r[lst] = py[j];
}
lst = py[j];
}
}
for (int j = k - 1; j > i; j--) {
int a = px[i], b = px[j];
int x1 = x[a], x2 = x[b];
if (qy[a] > qy[b]) {
std::swap(a, b);
}
if (r[a] == b) {
ans += get(x1, y[a], x2, y[b]);
if (l[a] != -1) {
ans -= get(x1, y[l[a]], x2, y[b]);
}
if (r[b] != -1) {
ans -= get(x1, y[a], x2, y[r[b]]);
}
if (l[a] != -1 && r[b] != -1) {
ans += get(x1, y[l[a]], x2, y[r[b]]);
}
}
a = px[j];
if (l[a] != -1) {
r[l[a]] = r[a];
}
if (r[a] != -1) {
l[r[a]] = l[a];
}
}
}
std::cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
input:
3 3 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
5 5 2 2 1 2 4
output:
126
result:
ok 1 number(s): "126"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
6 6 5 4 1 3 2 2 4 1 5 5 3
output:
161
result:
ok 1 number(s): "161"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
15 38 6 12 6 7 15 2 18 3 19 4 2 14 29
output:
80066
result:
ok 1 number(s): "80066"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
5145 5419 9 547 285 294 284 375 385 217 857 348 925 14 274 3104 853 184 953 794 603
output:
334363567
result:
ok 1 number(s): "334363567"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
5 5 16 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4
output:
25
result:
ok 1 number(s): "25"
Test #7:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
9145 9419 12 123 456 223 456 547 285 294 284 375 385 217 857 348 925 14 274 1104 853 184 953 794 603 2234 5678
output:
921360185
result:
ok 1 number(s): "921360185"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6 8 4 2 3 3 3 4 2 1 1
output:
444
result:
ok 1 number(s): "444"
Test #9:
score: 0
Accepted
time: 6155ms
memory: 3712kb
input:
1000000000 1000000000 5000 1657 1 1644 1 1000000 116362 1186 1 2392 1 1560 1 995 1 2340 1 1916 1 2143 1 1762 1 1000000 116109 1651 1 1000000 116059 2289 1 1000000 115730 1000000 115896 1000000 116499 1608 1 342 1 1000000 116949 1965 1 1000000 114571 1000000 116602 2171 1 1000000 114848 1000000 11627...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #10:
score: 0
Accepted
time: 6162ms
memory: 3764kb
input:
1000000000 1000000000 5000 1 2581 1 2273 115983 1000000 116105 1000000 114552 1000000 1 1955 1 2254 116061 1000000 116182 1000000 115783 1000000 114564 1000000 116614 1000000 116229 1000000 116087 1000000 114956 1000000 1 2453 114766 1000000 115750 1000000 115448 1000000 1 1748 116665 1000000 1 2237...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #11:
score: 0
Accepted
time: 6533ms
memory: 3716kb
input:
1000000000 1000000000 5000 824 1 811 1 2300000 114696 353 1 1559 1 727 1 162 1 1507 1 1083 1 1310 1 929 1 1000000 116109 818 1 1000000 116059 1456 1 1000000 115730 1000000 115896 2300000 114833 775 1 2300000 115576 2300000 115283 1132 1 1000000 114571 2300000 114936 1338 1 1000000 114848 2300000 114...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #12:
score: 0
Accepted
time: 6531ms
memory: 3796kb
input:
1000000000 1000000000 5000 1 1748 1 1440 115983 1000000 116105 1000000 114552 1000000 1 1122 1 1421 116061 1000000 114516 2300000 115783 1000000 114564 1000000 114948 2300000 114563 2300000 116087 1000000 114956 1000000 1 1620 114766 1000000 115750 1000000 115448 1000000 1 915 114999 2300000 1 1404 ...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #13:
score: 0
Accepted
time: 7777ms
memory: 3788kb
input:
1000000000 1000000000 5000 2300000 115622 1000000 116216 1000000 116852 2300000 115827 2300000 116715 1000000 116212 2300000 116390 2300000 114646 1000000 114857 2300000 116404 1000000 116398 1000000 115409 2300000 115721 1000000 116136 2300000 114925 2300000 114869 2300000 116176 1000000 115774 100...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #14:
score: 0
Accepted
time: 7834ms
memory: 3972kb
input:
1000000000 1000000000 5000 116495 1000000 116269 1000000 115204 2300000 115724 1000000 116508 1000000 115095 2300000 116712 1000000 114789 2300000 115009 2300000 114795 1000000 115093 2300000 115612 1000000 116183 2300000 116140 2300000 116148 2300000 115608 2300000 115111 1000000 115058 1000000 115...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #15:
score: 0
Accepted
time: 7948ms
memory: 3788kb
input:
999999992 999999990 5000 1035170 5702575 3959104 3959104 3887901 7432303 11377527 9794948 6282049 47695 11781994 2037659 11292228 47695 6787467 878630 10441683 5492431 1240650 1129736 5631557 11377527 4863442 5631557 6662382 4863442 8837935 7070049 8837935 10441683 4878561 5702575 5610718 2664505 58...
output:
892807048
result:
ok 1 number(s): "892807048"
Test #16:
score: -100
Time Limit Exceeded
input:
999999948 999999898 5000 6033860 10854965 57219333 28077882 18498300 33290576 34559919 16960059 40765867 73389700 9985342 17984966 54717579 26853732 13059544 23513592 56562634 27758141 19776481 35613289 6632028 11929378 14942564 7329745 7337824 13208993 33584464 60460021 13330979 6539654 32561958 58...