QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489585#9155. 集合rizynvu100 ✓328ms58812kbC++141.3kb2024-07-24 21:37:542024-07-24 21:37:55

Judging History

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

  • [2024-07-24 21:37:55]
  • 评测
  • 测评结果:100
  • 用时:328ms
  • 内存:58812kb
  • [2024-07-24 21:37:54]
  • 提交

answer

#include<bits/stdc++.h>
using ull = unsigned long long;
std::mt19937_64 Rand(std::chrono::steady_clock::now().time_since_epoch().count());
#define gc getchar
inline int read() {
   int x = 0, c = gc();
   while (! isdigit(c)) c = gc();
   while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
   return x;
}
const int maxn = 2e5 + 10, maxm = 6e5 + 10;
ull rd[maxn], val[2][maxm];
int a[2][maxn][3], R[maxn];
int main() {
   int n = read(), m = read(), q = read();
   for (int op : {0, 1})
      for (int i = 1; i <= n; i++)
         for (int j : {0, 1, 2})
            a[op][i][j] = read();
   for (int i = 1; i <= n; i++)
      rd[i] = Rand();
   std::unordered_map<ull, int> sum; int cnt = 0;
   auto upd = [&](ull x, int v) {
      cnt += ! sum[x], sum[x] += v, cnt -= ! sum[x];
   };
   auto add = [&](int id) {
      if (id > n) return ;
      for (int op : {0, 1})
         for (int i : {0, 1, 2}) {
            upd(val[op][a[op][id][i]], op ? -1 : 1);
            upd(val[op][a[op][id][i]] ^= rd[id], op ? 1 : -1);
         }
   };
   for (int l = 1, r = 0; l <= n; add(l++)) {
      while (r <= n && ! cnt) add(++r);
      R[l] = r - 1;
   }
   for (int l, r; q--; ) {
      l = read(), r = read();
      puts(r <= R[l] ? "Yes" : "No");
   }
   return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 10ms
memory: 7816kb

Pretest #10:

score: 5
Accepted
time: 9ms
memory: 7800kb

Pretest #11:

score: 5
Accepted
time: 270ms
memory: 56292kb

Pretest #12:

score: 5
Accepted
time: 248ms
memory: 54260kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 44ms
memory: 8276kb

Pretest #16:

score: 5
Accepted
time: 42ms
memory: 8116kb

Pretest #17:

score: 5
Accepted
time: 13ms
memory: 14196kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 317ms
memory: 55092kb

Pretest #20:

score: 5
Accepted
time: 328ms
memory: 58476kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 9ms
memory: 7688kb

Test #10:

score: 5
Accepted
time: 10ms
memory: 7808kb

Test #11:

score: 5
Accepted
time: 247ms
memory: 54288kb

Test #12:

score: 5
Accepted
time: 233ms
memory: 54604kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 48ms
memory: 8180kb

Test #16:

score: 5
Accepted
time: 47ms
memory: 8248kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 308ms
memory: 55700kb

Test #20:

score: 5
Accepted
time: 322ms
memory: 58812kb

Extra Test:

score: 0
Extra Test Passed