QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492825#9155. 集合zfs732100 ✓543ms58960kbC++231.7kb2024-07-26 16:25:212024-07-26 16:25:22

Judging History

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

  • [2024-07-26 16:25:22]
  • 评测
  • 测评结果:100
  • 用时:543ms
  • 内存:58960kb
  • [2024-07-26 16:25:21]
  • 提交

answer

/*
 * _|_|_|_|_|  _|_|_|_|    _|_|_|  _|_|_|_|_|  _|_|_|      _|_|
 *       _|    _|        _|                _|        _|  _|    _|
 *     _|      _|_|_|      _|_|          _|      _|_|        _|
 *   _|        _|              _|      _|            _|    _|
 * _|_|_|_|_|  _|        _|_|_|      _|        _|_|_|    _|_|_|_|
 */

#include <bits/stdc++.h>

std::mt19937_64 engine(
    std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
#ifdef LOCAL
  freopen("task.in", "r", stdin);
  freopen("task.out", "w", stdout);
  freopen("task.err", "w", stderr);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m, q, bad = 0;
  std::cin >> n >> m >> q;

  std::vector<std::array<int, 3>> a(n), b(n);
  for (auto &i: a) for (auto &j: i) std::cin >> j, j--;
  for (auto &i: b) for (auto &j: i) std::cin >> j, j--;

  std::vector<unsigned long long> val(n), A(m), B(m);
  std::unordered_map<unsigned long long, int> hash;
  for (int i = 0; i < n; i++) val[i] = engine();

  auto Insert = [&](auto val, int num) {
    bad -= hash[val] != 0;
    hash[val] += num;
    bad += hash[val] != 0;
  };

  auto Toggle = [&](int x) {
    if (x == n) return;
    for (int i = 0; i < 3; i++) {
      Insert(A[a[x][i]], -1);
      Insert(B[b[x][i]], +1);
      A[a[x][i]] ^= val[x];
      B[b[x][i]] ^= val[x];
      Insert(A[a[x][i]], +1);
      Insert(B[b[x][i]], -1);
    }
  };

  std::vector<int> pr(n);

  for (int l = 0, r = -1; l < n; Toggle(l++)) {
    while (r < n && bad == 0)
      Toggle(++r);
    pr[l] = r;
  }

  while (q--) {
    int l, r;
    std::cin >> l >> r, l--, r--;
    std::cout << (pr[l] <= r ? "No\n" : "Yes\n");
  }

  return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 3840kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 3560kb

Pretest #3:

score: 5
Accepted
time: 0ms
memory: 3844kb

Pretest #4:

score: 5
Accepted
time: 0ms
memory: 3844kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 3568kb

Pretest #6:

score: 5
Accepted
time: 0ms
memory: 3604kb

Pretest #7:

score: 5
Accepted
time: 0ms
memory: 3652kb

Pretest #8:

score: 5
Accepted
time: 0ms
memory: 3640kb

Pretest #9:

score: 5
Accepted
time: 19ms
memory: 3832kb

Pretest #10:

score: 5
Accepted
time: 20ms
memory: 3668kb

Pretest #11:

score: 5
Accepted
time: 455ms
memory: 55268kb

Pretest #12:

score: 5
Accepted
time: 441ms
memory: 52892kb

Pretest #13:

score: 5
Accepted
time: 0ms
memory: 4084kb

Pretest #14:

score: 5
Accepted
time: 2ms
memory: 4092kb

Pretest #15:

score: 5
Accepted
time: 99ms
memory: 4144kb

Pretest #16:

score: 5
Accepted
time: 103ms
memory: 4096kb

Pretest #17:

score: 5
Accepted
time: 24ms
memory: 8664kb

Pretest #18:

score: 5
Accepted
time: 20ms
memory: 9560kb

Pretest #19:

score: 5
Accepted
time: 543ms
memory: 53716kb

Pretest #20:

score: 5
Accepted
time: 479ms
memory: 58676kb

Final Tests

Test #1:

score: 5
Accepted
time: 0ms
memory: 3600kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 3612kb

Test #3:

score: 5
Accepted
time: 0ms
memory: 3604kb

Test #4:

score: 5
Accepted
time: 0ms
memory: 3680kb

Test #5:

score: 5
Accepted
time: 0ms
memory: 3564kb

Test #6:

score: 5
Accepted
time: 0ms
memory: 3676kb

Test #7:

score: 5
Accepted
time: 1ms
memory: 3580kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 3660kb

Test #9:

score: 5
Accepted
time: 15ms
memory: 3608kb

Test #10:

score: 5
Accepted
time: 19ms
memory: 3712kb

Test #11:

score: 5
Accepted
time: 344ms
memory: 53260kb

Test #12:

score: 5
Accepted
time: 383ms
memory: 51100kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 3964kb

Test #14:

score: 5
Accepted
time: 2ms
memory: 4348kb

Test #15:

score: 5
Accepted
time: 105ms
memory: 4088kb

Test #16:

score: 5
Accepted
time: 105ms
memory: 4200kb

Test #17:

score: 5
Accepted
time: 19ms
memory: 8608kb

Test #18:

score: 5
Accepted
time: 26ms
memory: 9700kb

Test #19:

score: 5
Accepted
time: 522ms
memory: 52764kb

Test #20:

score: 5
Accepted
time: 514ms
memory: 58960kb

Extra Test:

score: 0
Extra Test Passed