QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#319254 | #6673. Be Careful 2 | Ishy | TL | 11742ms | 728340kb | C++14 | 8.2kb | 2024-02-02 11:07:10 | 2024-02-02 11:07:10 |
Judging History
answer
// Sea, You & Me
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 998244353
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { if(a > b) a = b; }
template<typename T> void chkmx(T &a, const T b) { if(a < b) a = b; }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
int res = 1;
while(k)
{
if(k & 1) Mul(res, x);
k >>= 1, Sqr(x);
}
return res;
}
template<typename T> void read(T &x)
{
x = 0;
int f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = x * f;
}
const int N = 5e3 + 5;
const int INF = 1e9 + 7;
int n, m, K;
PII p[N];
struct Rec
{
int l, r, u, d;
Rec(const int L = 0, const int R = 0, const int U = 0, const int D = 0){
l = L, r = R, u = U, d = D;
}
friend bool operator < (Rec A, Rec B)
{
if(A.l != B.l) return A.l < B.l;
if(A.r != B.r) return A.r < B.r;
if(A.u != B.u) return A.u < B.u;
return A.d < B.d;
}
friend bool operator == (Rec A, Rec B)
{
return (A.l == B.l && A.r == B.r && A.u == B.u && A.d == B.d);
}
friend bool operator != (Rec A, Rec B)
{
return (A.l != B.l || A.r != B.r || A.u != B.u || A.d != B.d);
}
}a[N * N]; int cnt;
map<PII, int> mp;
map<int, int> mpx;
map<int, int> mpy;
int X[N], xcnt;
int Y[N], ycnt;
set<int> Sx[N];
set<int> Sy[N];
int calc_coef(int l, int r, int u, int d)
{
PII w = MP(l, d), x = MP(l, u), y = MP(r, u), z = MP(r, d);
int vw = mp[w], vx = mp[x], vy = mp[y], vz = mp[z];
int v1 = 0, v2 = 0, v3 = 0, v4 = 0;
SII it1 = Sx[mpx[l]].upper_bound(d); if(it1 != Sx[mpx[l]].end() && *it1 < u) v1 = 1;
SII it2 = Sy[mpy[u]].upper_bound(l); if(it2 != Sy[mpy[u]].end() && *it2 < r) v2 = 1;
SII it3 = Sx[mpx[r]].upper_bound(d); if(it3 != Sx[mpx[r]].end() && *it3 < u) v3 = 1;
SII it4 = Sy[mpy[d]].upper_bound(l); if(it4 != Sy[mpy[d]].end() && *it4 < r) v4 = 1;
// for(int i = l + 1; i < r; ++i)
// if(mpx.count(i))
// {
// SII it = Sx[mpx[i]].upper_bound(d);
// if(it != Sx[mpx[i]].end() && *it < u)
// assert(0);
// }
if(l == r && u == d) return -1;
if(l == r) return (v1 == 0 ? 1 : 0);
if(u == d) return (v2 == 0 ? 1 : 0);
int cnt = vw + vx + vy + vz;
int emp = (v1 == 0 && v2 == 0 && v3 == 0 && v4 == 0);
// choose 0
int res = (v1 == 1 && v2 == 1 && v3 == 1 && v4 == 1);
if(cnt == 0) return res;
// choose 1
if(vw == 1) res -= (v1 == 0 && v4 == 0 && v2 == 1 && v3 == 1);
if(vx == 1) res -= (v1 == 0 && v2 == 0 && v3 == 1 && v4 == 1);
if(vy == 1) res -= (v2 == 0 && v3 == 0 && v1 == 1 && v4 == 1);
if(vz == 1) res -= (v3 == 0 && v4 == 0 && v1 == 1 && v2 == 1);
// if(l == 1 && r == 4 && u == 3 && d == 2) cerr << "!!! " << res << '\n';
if(cnt == 1) return res;
// choose 2
if(vw == 1 && vx == 1) res -= (v1 == 0 && v2 == 0 && v4 == 0 && v3 == 1);
if(vx == 1 && vy == 1) res -= (v1 == 0 && v2 == 0 && v3 == 0 && v4 == 1);
if(vy == 1 && vz == 1) res -= (v2 == 0 && v3 == 0 && v4 == 0 && v1 == 1);
if(vz == 1 && vw == 1) res -= (v1 == 0 && v3 == 0 && v4 == 0 && v2 == 1);
if(vw == 1 && vy == 1) res += emp;
if(vx == 1 && vz == 1) res += emp;
if(cnt == 2) return res;
// choose 3
if(vw == 1 && vx == 1 && vy == 1) res -= emp;
if(vx == 1 && vy == 1 && vz == 1) res -= emp;
if(vy == 1 && vz == 1 && vw == 1) res -= emp;
if(vz == 1 && vw == 1 && vx == 1) res -= emp;
if(cnt == 3) return res;
if(vw == 1 && vx == 1 && vy == 1 && vz == 1) res += emp;
return res;
}
const int inv6 = qwqmi(6);
const int inv4 = qwqmi(4);
const int inv30 = qwqmi(30);
int sum2(int x) { return mul(inv6, mul(x, mul(x + 1, 2 * x + 1))); }
int sum3(int x) { return mul(inv4, mul(sqr(x), sqr(x + 1))); }
int sum4(int x) { return mul(inv30, mul(x, mul(x + 1, mul(2 * x + 1, dec(mul(3, mul(x, x + 1)), 1))))); }
int cx[2], cy[2]; // w(len) = c[0] + c[1] * len
int func(int l, int r)
{
assert(l <= r);
l = max(0, l - 1);
int c2 = mul(cx[0], cy[0]);
int c3 = inc(mul(cx[0], cy[1]), mul(cx[1], cy[0]));
int c4 = mul(cx[1], cy[1]);
int res = 0;
Inc(res, mul(c2, dec(sum2(r), sum2(l))));
Inc(res, mul(c3, dec(sum3(r), sum3(l))));
Inc(res, mul(c4, dec(sum4(r), sum4(l))));
return res;
};
int calc_val(int l, int r, int u, int d)
{
assert(l <= r);
assert(d <= u);
--l, ++r, --d, ++u;
if(l < 0 || d < 0 || r > n || u > m) return 0;
int mn = max(r - l, u - d), mx = min(n, m);
vector<int> vec = {mn, mx + 1, r + 1, u + 1, n - l + 1, m - d + 1};
sort(vec.begin(), vec.end());
auto coef = [&](int len, int l, int r, int lim, int *c)
{
if(len <= lim - l && len <= r) c[0] = l - r + 1, c[1] = 1;
else if(len <= lim - l && len > r) c[0] = l + 1, c[1] = 0;
else if(len > lim - l && len <= r) c[0] = lim - r + 1, c[1] = 0;
else c[0] = lim + 1, c[1] = -1;
if(c[0] < 0) c[0] += MOD;
if(c[1] < 0) c[1] += MOD;
};
int res = 0;
for(int i = 0; i + 1 < (int)vec.size(); ++i)
{
if(vec[i] < mn) continue;
if(vec[i] > mx) break;
if(vec[i] == vec[i + 1]) continue;
coef(vec[i], l, r, n, cx);
coef(vec[i], d, u, m, cy);
Inc(res, func(vec[i], vec[i + 1] - 1));
}
return res;
}
int main()
{
read(n), read(m), read(K);
for(int i = 1; i <= K; ++i)
{
read(p[i].fi), read(p[i].se);
X[++xcnt] = p[i].fi;
Y[++ycnt] = p[i].se;
mp[p[i]] = 1;
}
sort(p + 1, p + K + 1);
sort(X + 1, X + K + 1);
sort(Y + 1, Y + K + 1);
xcnt = unique(X + 1, X + K + 1) - (X + 1);
ycnt = unique(Y + 1, Y + K + 1) - (Y + 1);
for(int i = 1; i <= xcnt; ++i) mpx[X[i]] = i;
for(int i = 1; i <= ycnt; ++i) mpy[Y[i]] = i;
for(int i = 1; i <= K; ++i)
{
Sx[mpx[p[i].fi]].insert(p[i].se);
Sy[mpy[p[i].se]].insert(p[i].fi);
}
for(int i = 1; i <= K; ++i)
{
int U = INF, D = -INF;
a[++cnt] = Rec(p[i].fi, p[i].fi, p[i].se, p[i].se);
for(int j = i + 1; j <= K; ++j)
{
if(p[j].se >= U || p[j].se <= D) continue;
int mn = min(p[i].se, p[j].se);
int mx = max(p[i].se, p[j].se);
a[++cnt] = Rec(p[i].fi, p[j].fi, mx, mn);
a[++cnt] = Rec(p[i].fi, p[j].fi, mx, D);
a[++cnt] = Rec(p[i].fi, p[j].fi, U, mn);
a[++cnt] = Rec(p[i].fi, p[j].fi, U, D);
if(p[j].se >= p[i].se) U = p[j].se;
if(p[j].se <= p[i].se) D = p[j].se;
}
}
sort(a + 1, a + cnt + 1);
cnt = unique(a + 1, a + cnt + 1) - (a + 1);
cx[0] = n + 1, cx[1] = -1, cy[0] = m + 1, cy[1] = -1;
int ans = func(1, min(n, m));
for(int i = 1; i <= cnt; ++i)
{
if(a[i].u == INF) continue;
if(a[i].d == -INF) continue;
// cerr << a[i].l << ' ' << a[i].r << ' ' << a[i].u << ' ' << a[i].d << '\n';
int c = calc_coef(a[i].l, a[i].r, a[i].u, a[i].d);
int f = calc_val(a[i].l, a[i].r, a[i].u, a[i].d);
if(c < 0) c += MOD;
Inc(ans, mul(c, f));
// cerr << c << ' ' << f << '\n';
}
printf("%d", ans);
return 0;
}
/*
5 5 4
1 1
2 3
4 2
1 2
*/
/*
10 10 12
1 4
2 4
5 2
2 2
3 3
2 8
3 9
1 2
1 8
1 9
7 6
2 5
ans : 1115
*/
/*
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
ans : 921360185
*/
/*
100 100 40
13 77
15 17
74 83
25 51
49 65
60 19
83 86
71 87
47 2
7 31
34 65
84 32
58 69
89 92
67 61
49 79
92 74
76 87
96 37
45 21
56 84
53 72
16 30
59 41
55 9
31 72
86 53
95 53
80 87
51 99
55 83
13 93
3 90
61 83
65 27
66 57
52 34
3 46
6 30
92 80
ans : 12252760
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 19ms
memory: 395748kb
input:
3 3 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 20ms
memory: 395792kb
input:
5 5 2 2 1 2 4
output:
126
result:
ok 1 number(s): "126"
Test #3:
score: 0
Accepted
time: 24ms
memory: 395768kb
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: 11ms
memory: 395748kb
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: 11ms
memory: 395724kb
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: 23ms
memory: 395772kb
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: 32ms
memory: 395744kb
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: 27ms
memory: 395740kb
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: 40ms
memory: 396852kb
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: 47ms
memory: 396776kb
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: 1368ms
memory: 396756kb
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: 43ms
memory: 396692kb
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: 2752ms
memory: 396832kb
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: 36ms
memory: 396644kb
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: 179ms
memory: 396624kb
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: 0
Accepted
time: 11742ms
memory: 728340kb
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...
output:
461431823
result:
ok 1 number(s): "461431823"
Test #17:
score: -100
Time Limit Exceeded
input:
999999524 999999758 5000 28630401 15905366 49821653 27672863 52823763 29343863 14406464 29362320 3914600 2178863 15379626 31340404 2382937 4856861 26445243 14692595 15255307 8475517 23233725 12911959 8922530 4954657 80413834 44658470 59845170 33233185 38234833 21236207 48814787 27111180 7919671 4397...