QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505032#9155. 集合JCY_100 ✓283ms19956kbC++231.5kb2024-08-04 18:31:532024-08-04 18:31:54

Judging History

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

  • [2024-08-04 18:31:54]
  • 评测
  • 测评结果:100
  • 用时:283ms
  • 内存:19956kb
  • [2024-08-04 18:31:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  x = max(x, y);
}
template <typename T>
void chkmin(T &x, const T &y) {
  x = min(x, y);
}
constexpr int MAXN = 2e5 + 10, MAXM = 6e5 + 10;
int n, m, q, a[MAXN][3], b[MAXN][3], lim[MAXN];
ull val[MAXN], pa[MAXM], pb[MAXM];
mt19937_64 rng;
unordered_map<ull, int> mp;
void update(ull x, int y) {
  auto it = mp.find(x);
  if (it != mp.end()) {
    it->second += y;
    if (!it->second) mp.erase(it);
  } else {
    mp[x] = y;
  }
}
void insert(int p) {
  for (auto i : a[p]) {
    update(pa[i], -1);
    pa[i] ^= val[p];
    update(pa[i], 1);
  }
  for (auto i : b[p]) {
    update(pb[i], 1);
    pb[i] ^= val[p];
    update(pb[i], -1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) val[i] = rng();
  for (int i = 1; i <= n; ++i)
    for (auto &j : a[i]) cin >> j;
  for (int i = 1; i <= n; ++i)
    for (auto &j : b[i]) cin >> j;
  for (int i = 1, j = 1; i <= n; ++i) {
    insert(i);
    while (!mp.empty()) insert(j++);
    lim[i] = j;
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << (l >= lim[r] ? "Yes" : "No") << "\n";
  }
  return 0;
}
/*
g++ A.cpp -o A -std=c++17 -O2 -Wall -Wextra -Wshadow -g -fsanitize=address,undefined
*/

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 22ms
memory: 9744kb

Pretest #10:

score: 5
Accepted
time: 23ms
memory: 9772kb

Pretest #11:

score: 5
Accepted
time: 149ms
memory: 12092kb

Pretest #12:

score: 5
Accepted
time: 159ms
memory: 12532kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 113ms
memory: 9764kb

Pretest #16:

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

Pretest #17:

score: 5
Accepted
time: 12ms
memory: 11828kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 276ms
memory: 10960kb

Pretest #20:

score: 5
Accepted
time: 283ms
memory: 19956kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 145ms
memory: 11304kb

Test #12:

score: 5
Accepted
time: 154ms
memory: 12380kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 119ms
memory: 9756kb

Test #16:

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

Test #17:

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

Test #18:

score: 5
Accepted
time: 16ms
memory: 12668kb

Test #19:

score: 5
Accepted
time: 259ms
memory: 11816kb

Test #20:

score: 5
Accepted
time: 282ms
memory: 19940kb

Extra Test:

score: 0
Extra Test Passed