QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499505#9155. 集合Register_int100 ✓492ms65168kbC++141.4kb2024-07-31 15:02:332024-07-31 15:02:33

Judging History

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

  • [2024-07-31 15:02:33]
  • 评测
  • 测评结果:100
  • 用时:492ms
  • 内存:65168kb
  • [2024-07-31 15:02:33]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 6e5 + 10;

mt19937_64 eng(time(0));

int n, m, q, ans; unordered_map<ull, int> cnt;

ull w[MAXN], ha[MAXN], hb[MAXN]; int a[MAXN][3], b[MAXN][3], p[MAXN];

inline void add(ull x) { cnt[x]++ && --ans, cnt[x] && ++ans; }
inline void del(ull x) { cnt[x]-- && --ans, cnt[x] && ++ans; }

inline 
void upd(int i, int t) {
	del(ha[a[i][0]]), del(ha[a[i][1]]), del(ha[a[i][2]]);
	if (t == 1) ha[a[i][0]] += w[i], ha[a[i][1]] += w[i], ha[a[i][2]] += w[i];
	else ha[a[i][0]] -= w[i], ha[a[i][1]] -= w[i], ha[a[i][2]] -= w[i];
	add(ha[a[i][0]]), add(ha[a[i][1]]), add(ha[a[i][2]]);
	
	add(hb[b[i][0]]), add(hb[b[i][1]]), add(hb[b[i][2]]);
	if (t == 1) hb[b[i][0]] += w[i], hb[b[i][1]] += w[i], hb[b[i][2]] += w[i];
	else hb[b[i][0]] -= w[i], hb[b[i][1]] -= w[i], hb[b[i][2]] -= w[i];
	del(hb[b[i][0]]), del(hb[b[i][1]]), del(hb[b[i][2]]);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
	for (int i = 1; i <= n; i++) scanf("%d%d%d", &b[i][0], &b[i][1], &b[i][2]);
	for (int i = 1; i <= n; i++) w[i] = eng();
	for (int i = 1, j = 0; i <= n; i++) { for (; j <= n && !ans; upd(++j, 1)); p[i] = j, upd(i, -1); }
	for (int l, r; q--;) scanf("%d%d", &l, &r), puts(p[l] > r ? "Yes" : "No");
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 400ms
memory: 63348kb

Pretest #12:

score: 5
Accepted
time: 335ms
memory: 61424kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 107ms
memory: 10288kb

Pretest #16:

score: 5
Accepted
time: 108ms
memory: 10364kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 492ms
memory: 61124kb

Pretest #20:

score: 5
Accepted
time: 456ms
memory: 65168kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 428ms
memory: 61464kb

Test #12:

score: 5
Accepted
time: 380ms
memory: 57396kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 102ms
memory: 10192kb

Test #16:

score: 5
Accepted
time: 108ms
memory: 10648kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 441ms
memory: 58852kb

Test #20:

score: 5
Accepted
time: 462ms
memory: 63476kb

Extra Test:

score: 0
Extra Test Passed