QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502458#9155. 集合nhuang685100 ✓602ms63732kbC++201.9kb2024-08-03 06:27:402024-08-03 06:27:41

Judging History

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

  • [2024-08-03 06:27:41]
  • 评测
  • 测评结果:100
  • 用时:602ms
  • 内存:63732kb
  • [2024-08-03 06:27:40]
  • 提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-08-02 15:07:49
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
void bar() {}
#endif

std::mt19937_64
    rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::unordered_map<uint64_t, uint64_t> mp;
uint64_t get_hash(uint64_t val) {
  if (mp.contains(val)) {
    return mp[val];
  }
  return mp[val] = rng() % (1ULL << 56);
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<uint64_t> va(m), vb(m);
  std::vector<std::array<int, 3>> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      std::cin >> a[i][j];
      --a[i][j];
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      std::cin >> b[i][j];
      --b[i][j];
    }
  }
  uint64_t ta = m * get_hash(0), tb = m * get_hash(0);
  auto add_a = [&](int v, int pos) {
    ta -= get_hash(va[v]);
    va[v] ^= get_hash(pos);
    ta += get_hash(va[v]);
  };
  auto add_b = [&](int v, int pos) {
    tb -= get_hash(vb[v]);
    vb[v] ^= get_hash(pos);
    tb += get_hash(vb[v]);
  };
  std::vector<int> pl(n);
  {
    int l = 0;
    for (int r = 0; r < n; ++r) {
      for (int i = 0; i < 3; ++i) {
        add_a(a[r][i], r);
        add_b(b[r][i], r);
      }
      while (l < r && ta != tb) {
        for (int i = 0; i < 3; ++i) {
          add_a(a[l][i], l);
          add_b(b[l][i], l);
        }
        ++l;
      }
      assert(ta == tb);
      pl[r] = l;
    }
  }
  while ((q--) != 0) {
    int l, r;
    std::cin >> l >> r;
    --l;
    --r;
    if (pl[r] <= l) {
      std::cout << "Yes\n";
    } else {
      std::cout << "No\n";
    }
  }
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 524ms
memory: 60024kb

Pretest #12:

score: 5
Accepted
time: 459ms
memory: 57708kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 101ms
memory: 4028kb

Pretest #16:

score: 5
Accepted
time: 101ms
memory: 4204kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 602ms
memory: 58460kb

Pretest #20:

score: 5
Accepted
time: 534ms
memory: 63032kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 444ms
memory: 57912kb

Test #12:

score: 5
Accepted
time: 444ms
memory: 55788kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 104ms
memory: 4292kb

Test #16:

score: 5
Accepted
time: 106ms
memory: 4180kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 21ms
memory: 9472kb

Test #19:

score: 5
Accepted
time: 562ms
memory: 57480kb

Test #20:

score: 5
Accepted
time: 551ms
memory: 63732kb

Extra Test:

score: 0
Extra Test Passed