QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#493244#9155. 集合Survivor_winner100 ✓196ms26668kbC++141.2kb2024-07-26 22:42:322024-07-26 22:42:32

Judging History

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

  • [2024-07-26 22:42:32]
  • 评测
  • 测评结果:100
  • 用时:196ms
  • 内存:26668kb
  • [2024-07-26 22:42:32]
  • 提交

answer

// superyijin AK IOI
// wangsiyuanZP AK IOI
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937 Rand(time(0));
const int rnd = Rand();
unsigned int Hash(unsigned int x)
{
	x ^= rnd, x ^= (x << 7), x ^= (x >> 11), x ^= (x << 13), x ^= rnd;
	return x;
}
int hs, a[200010][3], b[200010][3], c[200010][3], pos[200010];
unsigned int sa[600010], sb[600010];
void upd(int x, int y)
{
	for (auto i : a[x])
	{
		hs -= Hash(sa[i]);
		sa[i] += Hash(x) * y;
		hs += Hash(sa[i]);
	}
	for (auto i : b[x])
	{
		hs += Hash(sb[i]);
		sb[i] += Hash(x) * y;
		hs -= Hash(sb[i]);
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];
	for (int i = 1; i <= n; i++) cin >> b[i][0] >> b[i][1] >> b[i][2];
	int r = 0;
	for (int l = 1; l <= n; l++)
	{
		if (l > 1) upd(l - 1, -1);
		while (r < n)
		{
			upd(r + 1, 1);
			if (hs != 0)
			{
				upd(r + 1, -1);
				break;
			}
			r++;
		}
		pos[l] = r;
	}
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		cout << (r <= pos[l] ? "Yes" : "No") << '\n';
	}
	return 0;
}
// superyijin AK IOI
// wangsiyuanZP AK IOI

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 69ms
memory: 18908kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 105ms
memory: 9880kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 175ms
memory: 17232kb

Pretest #20:

score: 5
Accepted
time: 196ms
memory: 26584kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 5
Accepted
time: 20ms
memory: 9824kb

Test #11:

score: 5
Accepted
time: 71ms
memory: 18012kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 181ms
memory: 15604kb

Test #20:

score: 5
Accepted
time: 193ms
memory: 26668kb

Extra Test:

score: 0
Extra Test Passed