QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505666#9155. 集合251Sec100 ✓460ms61204kbC++141.3kb2024-08-05 08:06:122024-08-05 08:06:12

Judging History

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

  • [2024-08-05 08:06:12]
  • 评测
  • 测评结果:100
  • 用时:460ms
  • 内存:61204kb
  • [2024-08-05 08:06:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
mt19937_64 eng(363415);
int n, m, q;
unordered_map<ll, int> f;
int g;
void UpdCnt(ll p, int x) {
	if (f[p]) g--;
	f[p] += x;
	if (f[p]) g++;
}
int a[600005], b[600005];
ull fa[600005], fb[600005], w[600005];
void Upd(int p, int x) {
	UpdCnt(fa[a[p * 3 - 2]], -1), UpdCnt(fa[a[p * 3 - 1]], -1), UpdCnt(fa[a[p * 3]], -1);
	fa[a[p * 3 - 2]] += w[p] * x;
	fa[a[p * 3 - 1]] += w[p] * x;
	fa[a[p * 3]] += w[p] * x;
	UpdCnt(fa[a[p * 3 - 2]], 1), UpdCnt(fa[a[p * 3 - 1]], 1), UpdCnt(fa[a[p * 3]], 1);
	UpdCnt(fb[b[p * 3 - 2]], 1), UpdCnt(fb[b[p * 3 - 1]], 1), UpdCnt(fb[b[p * 3]], 1);
	fb[b[p * 3 - 2]] += w[p] * x;
	fb[b[p * 3 - 1]] += w[p] * x;
	fb[b[p * 3]] += w[p] * x;
	UpdCnt(fb[b[p * 3 - 2]], -1), UpdCnt(fb[b[p * 3 - 1]], -1), UpdCnt(fb[b[p * 3]], -1);
}
int ans[600005];
int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++) w[i] = eng();
	for (int i = 1; i <= n * 3; i++) scanf("%d", a + i);
	for (int i = 1; i <= n * 3; i++) scanf("%d", b + i);
	for (int r = 1, l = 1; r <= n; r++) {
		Upd(r, 1);
		while (g) Upd(l++, -1);
		ans[r] = l;
	}
	while (q--) {
		int l, r; scanf("%d%d", &l, &r);
		puts(l >= ans[r] ? "Yes" : "No");
	}
	return 0;
} 

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 354ms
memory: 58180kb

Pretest #12:

score: 5
Accepted
time: 350ms
memory: 56824kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 103ms
memory: 10296kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 449ms
memory: 57552kb

Pretest #20:

score: 5
Accepted
time: 443ms
memory: 61204kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 18ms
memory: 9840kb

Test #10:

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

Test #11:

score: 5
Accepted
time: 350ms
memory: 56744kb

Test #12:

score: 5
Accepted
time: 347ms
memory: 54808kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 103ms
memory: 10152kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 460ms
memory: 56456kb

Test #20:

score: 5
Accepted
time: 437ms
memory: 60648kb

Extra Test:

score: 0
Extra Test Passed