QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200765 | #6673. Be Careful 2 | yllcm | WA | 1ms | 9904kb | C++14 | 5.4kb | 2023-10-04 19:39:57 | 2023-10-04 19:39:58 |
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(int x, int y, int z, int w) {
int coef = 0, res = 0;
if(x == y)coef = sum1[x][w] - sum1[x][z - 1];
else if(z == w)coef = sum2[z][y] - sum2[z][x - 1];
else {
coef += sum1[x][w] - sum1[x][z - 1];
coef += sum1[y][w] - sum1[y][z - 1];
coef += sum2[z][y] - sum2[z][x - 1];
coef += sum2[w][y] - sum2[w][x - 1];
coef -= (vis[x][z] + vis[x][w] + vis[y][z] + vis[y][w]);
}
coef = (coef & 1) ? P - 1 : 1;
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};
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;
int tv1 = 1, td1 = 0, tv2 = 1, td2 = 0;
int l = p[i], r = (i + 1 == p.size() ? min(n, m) : 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, l, r));
}
// 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++)A[a[i].FR].pb(i);
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);
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 = 1; j <= k; j++)if(a[j].FR > a[i].FR)cnt[a[j].SE]++;
for(int j = 1; j <= tot2; j++)if(!cnt[j])ufs.del(j);
for(int j = tot1; j >= a[i].FR; j--) {
if(j > a[i].FR)for(int t : A[j])if(!(--cnt[a[t].SE]))ufs.del(a[t].SE);
for(int t : A[j])if(j > a[i].FR || a[t].SE > a[i].SE) {
if(ufs.ql(a[t].SE) > a[i].SE)continue;
int nl = a[i].SE, nr = a[t].SE;
int tl = ufs.ql(nl), tr = ufs.qr(nr);
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));
}
}
}
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: 7872kb
input:
3 3 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9904kb
input:
5 5 2 2 1 2 4
output:
126
result:
ok 1 number(s): "126"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 7880kb
input:
6 6 5 4 1 3 2 2 4 1 5 5 3
output:
998243965
result:
wrong answer 1st numbers differ - expected: '161', found: '998243965'