QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563866#6673. Be Careful 2liuziaoWA 2ms5968kbC++236.8kb2024-09-14 16:30:562024-09-14 16:30:56

Judging History

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

  • [2024-09-14 16:30:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5968kb
  • [2024-09-14 16:30:56]
  • 提交

answer

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxK = 5e3 + 5, kMod = 998244353;

int n, m, k, cx, cy;
int x[kMaxK], y[kMaxK], unqx[kMaxK], unqy[kMaxK], cnt[kMaxK][kMaxK];
int nxt[kMaxK], pre[kMaxK];
std::vector<int> vec[kMaxK];
       bool vis[kMaxK][kMaxK] = {0};

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1) ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int fix(int x) { return (x % kMod + kMod) % kMod; }
inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

int getop(int x) { return (~x & 1) ? 1 : (kMod - 1); }

int calc1(int x) {
  static constexpr int kInv2 = qpow(2);
  return 1ll * x * (x + 1) % kMod * kInv2 % kMod;
}
int calc1(int l, int r) { return (l <= r) ? sub(calc1(r), calc1(l - 1)) : 0; }

int calc2(int x) {
  static constexpr int kInv6 = qpow(6);
  return 1ll * x * (x + 1) % kMod * (2ll * x + 1) % kMod * kInv6 % kMod;
}
int calc2(int l, int r) { return (l <= r) ? sub(calc2(r), calc2(l - 1)) : 0; }

int calc3(int x) {
  int sum = calc1(x);
  return 1ll * sum * sum % kMod;
}
int calc3(int l, int r) { return (l <= r) ? sub(calc3(r), calc3(l - 1)) : 0; }

int calc4(int x) {
  static constexpr int kInv30 = qpow(30);
  return 1ll * x * (x + 1) % kMod * (2 * x + 1) % kMod *
         ((3ll * x * x + 3ll * x + kMod - 1) % kMod) % kMod * kInv30 % kMod;
}
int calc4(int l, int r) { return (l <= r) ? sub(calc4(r), calc4(l - 1)) : 0; }

int calc(int k1, int b1, int k2, int b2, int l, int r) {
  // int sum2 = 1ll * b1 * b2 % kMod * calc2(l, r) % kMod;
  // int sum3 = 1ll * add(1ll * k1 * b2 % kMod, 1ll * k2 * b1 % kMod) * calc3(l, r) % kMod;
  // int sum4 = 1ll * k1 * k2 % kMod * calc4(l, r) % kMod;
  // return add(sum2, add(sum3, sum4));

  int ret = 0;
  for (int i = l; i <= r; ++i) inc(ret, 1ll * i * i % kMod * (1ll * k1 * i % kMod + b1) % kMod * ((1ll * k2 * i % kMod + b2) % kMod) % kMod);
  return ret;
}

int getcnt(int _x1, int _y1, int _x2, int _y2) {
  if (_x1 > _x2 || _y1 > _y2) return 0;
  return cnt[_x2][_y2] - cnt[_x1 - 1][_y2] - cnt[_x2][_y1 - 1] +
         cnt[_x1 - 1][_y1 - 1];
}

bool check(int _x1, int _y1, int _x2, int _y2) {
  if (_x1 > _x2 || _y1 > _y2) return 0;
  return !getcnt(_x1 + 1, _y1 + 1, _x2 - 1, _y2 - 1) &&
         getcnt(_x1, _y1, _x1, _y2) && getcnt(_x1, _y2, _x2, _y2) &&
         getcnt(_x2, _y1, _x2, _y2) && getcnt(_x1, _y1, _x2, _y1);
}

int solve(int _x1, int _y1, int _x2, int _y2) {
  if (_x1 > _x2 || _y1 > _y2) return 0;
  // std::cerr << getcnt(_x1, _y1, _x2, _y2) << " : ";
  _x1 = unqx[_x1], _y1 = unqy[_y1], _x2 = unqx[_x2], _y2 = unqy[_y2];
  int l = std::max(_x2 - _x1 + 2, _y2 - _y1 + 2), r = std::min(n, m);
  if (l > r) return 0;
  std::vector<int> v = {l, r + 1, _x2 + 1, n - _x1 + 1, _y2 + 1, m - _y1 + 1};
  std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end());
  int ret = 0;
  for (int i = 0; i + 1 < (int)v.size(); ++i) {
    if (v[i] >= l && v[i] < r + 1) {
      int L = v[i], R = v[i + 1] - 1, kx = 0, bx = 0, ky = 0, by = 0;
      if (_x1 - 1 <= n - R) inc(bx, _x1 - 1);
      else dec(kx, 1), inc(bx, n);
      if (0 <= _x2 - R + 1) inc(kx, 1), dec(bx, _x2);
      else inc(bx, 1);

      if (_y1 - 1 <= m - R) inc(by, _y1 - 1);
      else dec(ky, 1), inc(by, m);
      if (0 <= _y2 - R + 1) inc(ky, 1), dec(by, _y2);
      else inc(by, 1);

      inc(ret, calc(kx, bx, ky, by, L, R));
    }
  }
  // std::cerr << _x1 << ' ' << _y1 << ' ' << _x2 << ' ' << _y2 << ' ' << ret << '\n';
  return ret;
}

void discrete() {
  std::sort(unqx + 1, unqx + 1 + cx);
  cx = std::unique(unqx + 1, unqx + 1 + cx) - (unqx + 1);
  std::sort(unqy + 1, unqy + 1 + cy);
  cy = std::unique(unqy + 1, unqy + 1 + cy) - (unqy + 1);
  for (int i = 1; i <= k; ++i) {
    x[i] = std::lower_bound(unqx + 1, unqx + 1 + cx, x[i]) - unqx;
    y[i] = std::lower_bound(unqy + 1, unqy + 1 + cy, y[i]) - unqy;
    ++cnt[x[i]][y[i]], vec[x[i]].emplace_back(y[i]);
  }
}

void del(int x) {
  if (pre[x]) nxt[pre[x]] = nxt[x];
  if (nxt[x]) pre[nxt[x]] = pre[x];
  pre[x] = nxt[x] = 0;
}

void dickdreamer() {
  std::cin >> n >> m >> k;
  for (int i = 1; i <= k; ++i) {
    std::cin >> x[i] >> y[i];
    unqx[++cx] = x[i], unqy[++cy] = y[i];
  }
  discrete();
  for (int i = 1; i <= cx; ++i)
    for (int j = 1; j <= cy; ++j)
      cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
  int ans = calc(kMod - 1, n + 1, kMod - 1, m + 1, 1, std::min(n, m));
  // std::cerr << ans << '\n';
  for (int i = 1; i <= cx; ++i) {
    static int cnt[kMaxK] = {0};
    memset(cnt, 0, sizeof(cnt));
    for (int j = 1; j <= k; ++j)
      if (x[j] >= i)
        ++cnt[y[j]];
    int lst = 0;
    std::fill_n(pre + 1, cy, 0);
    std::fill_n(nxt + 1, cy, 0);
    for (int j = 1; j <= cy; ++j) {
      if (cnt[j]) {
        if (lst) nxt[lst] = j, pre[j] = lst;
        lst = j;
      }
    }
    for (int j = cx; j >= i; --j) {
      std::vector<std::pair<int, int>> v;
      for (auto sx : vec[i]) {
        for (auto sy : vec[j]) {
          if (i == j && (sx > sy)) continue;
          int x = sx, y = sy;
          if (x > y) std::swap(x, y);
          if (pre[x] && nxt[y] && !vis[pre[x]][nxt[y]] && check(i, pre[x], j, nxt[y])) {
            vis[pre[x]][nxt[y]] = 1, v.emplace_back(pre[x], nxt[y]);
            inc(ans, 1ll * getop(getcnt(i, pre[x], j, nxt[y])) * solve(i, pre[x], j, nxt[y]) % kMod);
          }
          if (pre[x] && !vis[pre[x]][y] && check(i, pre[x], j, y)) {
            vis[pre[x]][y] = 1, v.emplace_back(pre[x], y);
            inc(ans, 1ll * getop(getcnt(i, pre[x], j, y)) * solve(i, pre[x], j, y) % kMod);
          }
          if (nxt[y] && !vis[x][nxt[y]] && check(i, x, j, nxt[y])) {
            vis[x][nxt[y]] = 1, v.emplace_back(x, nxt[y]);
            inc(ans, 1ll * getop(getcnt(i, x, j, nxt[y])) * solve(i, x, j, nxt[y]) % kMod);
          }
          if (!vis[x][y] && check(i, x, j, y)) {
            vis[x][y] = 1, v.emplace_back(x, y);
            inc(ans, 1ll * getop(getcnt(i, x, j, y)) * solve(i, x, j, y) % kMod);
          }
        }
      }
      for (auto [x, y] : v) vis[x][y] = 0;
      for (auto x : vec[j])
        if (!--cnt[x])
          del(x);
    }
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5700kb

input:

3 3 1
2 2

output:

21

result:

ok 1 number(s): "21"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5652kb

input:

5 5 2
2 1
2 4

output:

126

result:

ok 1 number(s): "126"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5660kb

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: 1ms
memory: 5732kb

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: 2ms
memory: 5968kb

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: -100
Wrong Answer
time: 1ms
memory: 5720kb

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:

1271

result:

wrong answer 1st numbers differ - expected: '25', found: '1271'