QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488129#9155. 集合Xiaohuba100 ✓66ms21776kbC++234.0kb2024-07-23 16:58:162024-07-23 16:58:18

Judging History

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

  • [2024-07-23 16:58:18]
  • 评测
  • 测评结果:100
  • 用时:66ms
  • 内存:21776kb
  • [2024-07-23 16:58:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128

#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
#endif

#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define _loop_i_t(j, k) make_signed_t<decltype((j) - (k))>
#define For(i, j, k) for (_loop_i_t(j, k) i = (j); i <= (k); ++i) // NOLINT
#define ForDown(i, j, k)                                                       \
  for (_loop_i_t(j, k) i = (j); i >= decltype(i)(k); --i) // NOLINT
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
CONSTEXPR_FUNC il ll qpow(ll x, ull y, ll mod){ ll ans = 1; x %= mod; while (y) { if (y & 1) (ans *= x) %= mod; (x *= x) %= mod; y >>= 1; } return ans; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y); }
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } x *= f; }
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x), read(y...); }
// clang-format on

// File head end

namespace {
constexpr ll MAXN = 2e5 + 5, MAXM = 6e5 + 5, p1 = 998244353, p2 = 1e9 + 7;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n, m, q, a[MAXN][3], b[MAXN][3], ans[MAXN];
ll msk = rnd(), b1, b2, pw1[MAXN], pw2[MAXN], v1[MAXM], v2[MAXM];

il void init(ll &x, const ll p, ll *pw) {
  x = uniform_int_distribution<>(2333, p - 2333)(rnd), pw[0] = 1;
  For(i, 1, n) pw[i] = pw[i - 1] * x % p;
}
uint xorshift(uint x) {
  x ^= msk;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= msk;
  return x;
}

il void Main() {
  read(n, m, q);
  For(i, 1, n) read(a[i][0], a[i][1], a[i][2]);
  For(i, 1, n) read(b[i][0], b[i][1], b[i][2]);
  init(b1, p1, pw1), init(b2, p2, pw2);

  uint cur1 = 0, cur2 = 0;
  auto ins = [&](int i) {
    For(o, 0, 2) {
      cur1 -= xorshift(v1[a[i][o]]);
      v1[a[i][o]] += pw1[i];
      cur1 += xorshift(v1[a[i][o]]);
    }
    For(o, 0, 2) {
      cur2 -= xorshift(v2[b[i][o]]);
      v2[b[i][o]] += pw1[i];
      cur2 += xorshift(v2[b[i][o]]);
    }
  };
  auto del = [&](int i) {
    For(o, 0, 2) {
      cur1 -= xorshift(v1[a[i][o]]);
      v1[a[i][o]] -= pw1[i];
      cur1 += xorshift(v1[a[i][o]]);
    }
    For(o, 0, 2) {
      cur2 -= xorshift(v2[b[i][o]]);
      v2[b[i][o]] -= pw1[i];
      cur2 += xorshift(v2[b[i][o]]);
    }
  };
  for (int i = 1, j = 1; i <= n; i++) {
    ins(i);
    while (j <= i && cur1 != cur2)
      del(j++);
    ans[i] = j;
  }
  while (q--) {
    int x, y;
    read(x, y);
    cout << (x >= ans[y] ? "Yes" : "No") << '\n';
  }
}
} // namespace

signed main() { return Main(), 0; }

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

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

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 46ms
memory: 12016kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 57ms
memory: 12840kb

Pretest #20:

score: 5
Accepted
time: 66ms
memory: 21776kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 5
Accepted
time: 7ms
memory: 11808kb

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 40ms
memory: 11888kb

Test #16:

score: 5
Accepted
time: 41ms
memory: 11900kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 66ms
memory: 13824kb

Test #20:

score: 5
Accepted
time: 57ms
memory: 21632kb

Extra Test:

score: 0
Extra Test Passed