QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200828 | #6673. Be Careful 2 | yllcm | ML | 4470ms | 631412kb | C++14 | 6.7kb | 2023-10-04 20:57:30 | 2023-10-04 20:57:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define mp make_pair
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 5e3 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int n, m, k;
int tot1, tot2;
int ls1[N], ls2[N];
pii a[N];
void disc() {
for(int i = 1; i <= k; i++)ls1[++tot1] = a[i].FR;
for(int i = 1; i <= k; i++)ls2[++tot2] = a[i].SE;
sort(ls1 + 1, ls1 + 1 + tot1);
tot1 = unique(ls1 + 1, ls1 + 1 + tot1) - (ls1 + 1);
sort(ls2 + 1, ls2 + 1 + tot2);
tot2 = unique(ls2 + 1, ls2 + 1 + tot2) - (ls2 + 1);
for(int i = 1; i <= k; i++) {
a[i].FR = lower_bound(ls1 + 1, ls1 + 1 + tot1, a[i].FR) - ls1;
a[i].SE = lower_bound(ls2 + 1, ls2 + 1 + tot2, a[i].SE) - ls2;
}
return ;
}
vector<int> A[N];
struct UFS {
int L[N], R[N];
void init() {
for(int i = 1; i <= tot2 + 1; i++)L[i] = R[i] = i;
return ;
}
int ql(int x) {return L[x] == x ? x : L[x] = ql(L[x]);}
int qr(int x) {return R[x] == x ? x : R[x] = qr(R[x]);}
void del(int x) {L[x] = x - 1; R[x] = x + 1;}
}ufs;
int sum1[N][N], sum2[N][N], vis[N][N];
int calc2(int l, int r) {
int i6 = 166374059, res = 0;
auto _calc = [&](int r) {
int v1 = 1ll * r * (r + 1) % P, v2 = (2ll * r + 1) % P;
return 1ll * v1 * v2 % P * i6 % P;
};
add(res, _calc(r)); sub(res, _calc(l - 1));
return res;
}
int calc3(int l, int r) {
int i2 = 499122177, res = 0;
auto _calc = [&](int r) {
int v = 1ll * r * (r + 1) % P * i2 % P;
return 1ll * v * v % P;
};
add(res, _calc(r)); sub(res, _calc(l - 1));
return res;
}
int calc4(int l, int r) {
int i30 = 432572553, res = 0;
auto _calc = [&](int r) {
int v1 = 1ll * r * (r + 1) % P;
int v2 = (2ll * r + 1) % P;
int v3 = (3ll * r % P * r % P + 3ll * r - 1) % P;
return 1ll * v1 * v2 % P * v3 % P * i30 % P;
};
add(res, _calc(r)); sub(res, _calc(l - 1));
return res;
}
int Calc(int tv1, int td1, int tv2, int td2, int l, int r) {
int res = 0;
add(res, 1ll * tv1 * tv2 % P * calc2(l, r) % P);
add(res, 1ll * (1ll * tv1 * td2 % P + 1ll * tv2 * td1 % P) % P * calc3(l, r) % P);
add(res, 1ll * td1 * td2 % P * calc4(l, r) % P);
return res;
}
int calc_coef(int x, int y, int z, int w) {
int coef = 0;
if(x == y && z == w)coef = P - 1;
else if(x == y)coef = (sum1[x][w - 1] - sum1[x][z] ? 0 : 1);
else if(z == w)coef = (sum2[y - 1][z] - sum2[x][z] ? 0 : 1);
else {
vector<pii> p;
if(vis[x][z])p.pb(mp(0, 0));
if(vis[x][w])p.pb(mp(0, 2));
if(vis[y][z])p.pb(mp(2, 0));
if(vis[y][w])p.pb(mp(2, 2));
if(sum1[x][w - 1] - sum1[x][z])p.pb(mp(0, 1));
if(sum1[y][w - 1] - sum1[y][z])p.pb(mp(2, 1));
if(sum2[y - 1][z] - sum2[x][z])p.pb(mp(1, 0));
if(sum2[y - 1][w] - sum2[x][w])p.pb(mp(1, 2));
int f[3][3][3][3] = {0};
for(auto t : p) {
int u = t.FR, v = t.SE;
// printf("%d %d\n", u, v);
for(int i = 0; i < 3; i++) {
for(int j = 2; j >= i; j--) {
for(int k = 0; k < 3; k++) {
for(int l = 2; l >= k; l--) {
// printf("qwq:%d\n", f[i][j][k][l]);
int ni = min(i, u), nj = max(j, u);
int nk = min(k, v), nl = max(l, v);
sub(f[ni][nj][nk][nl], f[i][j][k][l]);
}
}
}
}
sub(f[u][u][v][v], 1);
}
coef = f[0][2][0][2];
}
return coef;
}
int calc(int x, int y, int z, int w) {
int coef = calc_coef(x, y, z, w), res = 0;
x = ls1[x]; y = ls1[y]; z = ls2[z]; w = ls2[w];
int st = max(y - x + 2, w - z + 2);
vector<int> p = {st, y + 1, n - x + 1, w + 1, m - z + 1, min(n, m) + 1};
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
// printf("st:%d\n", st);
for(int i = 0; i < p.size(); i++) {
if(p[i] < st)continue;
if(p[i] > min(n, m))continue;
int tv1 = 1, td1 = 0, tv2 = 1, td2 = 0;
int l = p[i], r = p[i + 1] - 1;
if(l > r)continue;
(x - 1 < n - p[i] ? add(tv1, x - 1) : (add(tv1, n), sub(td1, 1)));
(y - p[i] + 1 > 0 ? (sub(tv1, y + 1), add(td1, 1)) : void());
(z - 1 < m - p[i] ? add(tv2, z - 1) : (add(tv2, m), sub(td2, 1)));
(w - p[i] + 1 > 0 ? (sub(tv2, w + 1), add(td2, 1)) : void());
add(res, Calc(tv1, td1, tv2, td2, l, r));
// printf("range:%d %d %d\n", l, r, Calc(tv1, td1, tv2, td2, 5, 5));
}
// printf("calc:%d %d %d %d %d %d\n", x, y, z, w, coef, res);
return 1ll * res * coef % P;
}
int main() {
n = read(); m = read(); k = read();
for(int i = 1; i <= k; i++)a[i].FR = read(), a[i].SE = read();
disc();
for(int i = 1; i <= k; i++) {
vis[a[i].FR][a[i].SE] = 1;
sum1[a[i].FR][a[i].SE] = 1;
sum2[a[i].FR][a[i].SE] = 1;
}
for(int i = 1; i <= tot1; i++) {
for(int j = 1; j <= tot2; j++) {
sum1[i][j] += sum1[i][j - 1];
sum2[i][j] += sum2[i - 1][j];
}
}
int ans = Calc(n + 1, P - 1, m + 1, P - 1, 1, min(n, m));
// printf("ans:%d\n", ans);
sort(a + 1, a + 1 + k);
vector<array<int, 4> > rec;
for(int i = 1; i <= k; i++)rec.pb({a[i].FR, a[i].FR, a[i].SE, a[i].SE});
// for(int i = 1; i <= k; i++)add(ans, calc(a[i].FR, a[i].FR, a[i].SE, a[i].SE));
for(int i = 1; i <= k; i++) {
ufs.init();
vector<int> cnt(tot2 + 1);
for(int j = i + 1; j <= k; j++)cnt[a[j].SE]++;
for(int j = 1; j <= tot2; j++)if(!cnt[j])ufs.del(j);
for(int t = k; t > i; t--) {
if(!(--cnt[a[t].SE]))ufs.del(a[t].SE);
if(ufs.ql(a[t].SE - 1) > a[i].SE)continue;
if(ufs.ql(a[i].SE - 1) > a[t].SE)continue;
int nl = min(a[i].SE, a[t].SE), nr = max(a[i].SE, a[t].SE);
int tl = ufs.ql(nl), tr = ufs.qr(nr);
// printf("id:%d %d %d %d\n", i, t, tl, tr);
rec.pb({a[i].FR, a[t].FR, nl, nr});
if(tl)rec.pb({a[i].FR, a[t].FR, tl, nr});
if(tr <= tot2)rec.pb({a[i].FR, a[t].FR, nl, tr});
if(tl && tr <= tot2)rec.pb({a[i].FR, a[t].FR, tl, tr});
// add(ans, calc(a[i].FR, a[t].FR, nl, nr));
// if(tl)add(ans, calc(a[i].FR, a[t].FR, tl, nr));
// if(tr <= tot2)add(ans, calc(a[i].FR, a[t].FR, nl, tr));
// if(tl && tr <= tot2)add(ans, calc(a[i].FR, a[t].FR, tl, tr));
}
}
sort(rec.begin(), rec.end());
rec.erase(unique(rec.begin(), rec.end()), rec.end());
for(auto t : rec)add(ans, calc(t[0], t[1], t[2], t[3]));
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8256kb
input:
3 3 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 1ms
memory: 8056kb
input:
5 5 2 2 1 2 4
output:
126
result:
ok 1 number(s): "126"
Test #3:
score: 0
Accepted
time: 1ms
memory: 8072kb
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: 0ms
memory: 10048kb
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: 1ms
memory: 8088kb
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: 7996kb
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: 2ms
memory: 10000kb
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: 1ms
memory: 7884kb
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: 3201ms
memory: 418368kb
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: 2843ms
memory: 418052kb
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: 3150ms
memory: 368788kb
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: 4470ms
memory: 631412kb
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: 3620ms
memory: 271868kb
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: -100
Memory Limit Exceeded
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