QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498880#9155. 集合Floze3100 ✓182ms20100kbC++172.9kb2024-07-30 20:58:382024-07-30 20:58:40

Judging History

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

  • [2024-07-30 20:58:40]
  • 评测
  • 测评结果:100
  • 用时:182ms
  • 内存:20100kb
  • [2024-07-30 20:58:38]
  • 提交

answer

// Author: Floze3
// Time: 2024-07-30 20:34:33
// Problem: P10785 [NOI2024] 集合
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10785
// Memory Limit:  MB
// Time Limit:  ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define mp(x, y) std::make_pair(x, y)
#define eb emplace_back
#define fi first
#define se second
#define il inline
#define all(x) x.begin(), x.end()
#define file(name)                 \
  freopen(name ".in", "r", stdin); \
  freopen(name ".out", "w", stdout);

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;

#ifndef ONLINE_JUDGE
#define debug(x) \
  std::cerr << "In Line " << __LINE__ << ": " << #x << " = " << x << std::endl
#define look_time std::cerr << clock() * 1e3 / CLOCKS_PER_SEC << " ms\n"
#define look_memory std::cerr << fabs(&med - &mst) / 1024.0 / 1024.0 << " mb\n"
#else
#define debug(...) 42
#define look_time 42
#define look_memory 42
#endif

const int N = 2e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;

std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

bool mst;

const ull msk = rng();

ull sa, sb, ap[N * 3], bp[N * 3], mp[N];
int n, m, q, rm[N], a[N][3], b[N][3];

il ull sft(ull x) {
  if (!x) return x;
  x ^= msk;
  x ^= x << 7;
  x ^= x >> 11;
  x ^= x << 13;
  return x;
}

il void del(int pos) {
  for (int i = 0; i < 3; ++i) {
    sa -= sft(ap[a[pos][i]]);
    ap[a[pos][i]] -= mp[pos];
    sa += sft(ap[a[pos][i]]);
  }
  for (int i = 0; i < 3; ++i) {
    sb -= sft(bp[b[pos][i]]);
    bp[b[pos][i]] -= mp[pos];
    sb += sft(bp[b[pos][i]]);
  }
  return ;
}

il void add(int pos) {
  for (int i = 0; i < 3; ++i) {
    sa -= sft(ap[a[pos][i]]);
    ap[a[pos][i]] += mp[pos];
    sa += sft(ap[a[pos][i]]);
  }
  for (int i = 0; i < 3; ++i) {
    sb -= sft(bp[b[pos][i]]);
    bp[b[pos][i]] += mp[pos];
    sb += sft(bp[b[pos][i]]);
  }
  return ;
}

bool med;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  std::cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 3; ++j) std::cin >> a[i][j];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 3; ++j) std::cin >> b[i][j];
  }
  for (int i = 1; i <= n; ++i) mp[i] = rng();
  for (int i = 1; i <= n; ++i) rm[i] = n;
  add(1);
  for (int i = 1, j = 1; i <= n; del(i++)) {
    while (j <= n && sa == sb) {
      ++j;
      if (j <= n) add(j);
    }
    rm[i] = std::min(rm[i], j - 1);
  }
//  for (int i = 1; i <= n; ++i) std::cout << i << ' ' << rm[i] << '\n';
  while (q--) {
    int l, r;
    std::cin >> l >> r;
    std::cout << (r <= rm[l] ? "Yes\n" : "No\n");
  }
  return 0;
}

/*
all the things you do
the words you say
will all come back to you
*/

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 63ms
memory: 11116kb

Pretest #12:

score: 5
Accepted
time: 59ms
memory: 10988kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 98ms
memory: 7760kb

Pretest #16:

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

Pretest #17:

score: 5
Accepted
time: 6ms
memory: 8100kb

Pretest #18:

score: 5
Accepted
time: 8ms
memory: 10912kb

Pretest #19:

score: 5
Accepted
time: 167ms
memory: 11704kb

Pretest #20:

score: 5
Accepted
time: 182ms
memory: 20100kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 56ms
memory: 11812kb

Test #12:

score: 5
Accepted
time: 64ms
memory: 10880kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 98ms
memory: 7828kb

Test #16:

score: 5
Accepted
time: 96ms
memory: 7936kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 4ms
memory: 10968kb

Test #19:

score: 5
Accepted
time: 162ms
memory: 12108kb

Test #20:

score: 5
Accepted
time: 174ms
memory: 19968kb

Extra Test:

score: 0
Extra Test Passed