QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200765#6673. Be Careful 2yllcmWA 1ms9904kbC++145.4kb2023-10-04 19:39:572023-10-04 19:39:58

Judging History

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

  • [2023-10-04 19:39:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9904kb
  • [2023-10-04 19:39:57]
  • 提交

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'