QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200828#6673. Be Careful 2yllcmML 4470ms631412kbC++146.7kb2023-10-04 20:57:302023-10-04 20:57:30

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 20:57:30]
  • 评测
  • 测评结果:ML
  • 用时:4470ms
  • 内存:631412kb
  • [2023-10-04 20:57:30]
  • 提交

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

result: