QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491282#9155. 集合yushanen100 ✓406ms58780kbC++231.1kb2024-07-25 18:22:242024-07-25 18:22:24

Judging History

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

  • [2024-07-25 18:22:24]
  • 评测
  • 测评结果:100
  • 用时:406ms
  • 内存:58780kb
  • [2024-07-25 18:22:24]
  • 提交

answer

#include <iostream>
#include <unordered_map>
#include <random>
using namespace std;
const int N = 2e5 + 10, M = 6e5 + 10;
int n, m, q, x, y, a[N][3], b[N][3], cur, req[N];
using ull = unsigned long long;
unordered_map<ull, int> mp;
random_device rd;
mt19937 mt(rd());
ull sg[N], pa[M], pb[M];
void upd(ull x, int v)
{
	cur += !mp[x];
	mp[x] += v;
	cur -= !mp[x];
}
void acs(int x, int v)
{
	for (int i = 0; i < 3; i++)
	{
		upd(pa[a[x][i]], -1);
		pa[a[x][i]] += v * sg[x];
		upd(pa[a[x][i]], 1);

		upd(pb[b[x][i]], 1);
		pb[b[x][i]] += v * sg[x];
		upd(pb[b[x][i]], -1);
	}
}
int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			scanf("%d", a[i] + j);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			scanf("%d", b[i] + j);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		sg[i] = mt();
	}
	for (int i = 1, j = 1; i <= n; i++)
	{
		acs(i, 1);
		while (cur)
			acs(j, -1), j++;
		req[i] = j;
	}
	for (int i = 1; i <= q; i++)
	{
		scanf("%d%d", &x, &y);
		puts(req[y] <= x ? "Yes" : "No");
	}
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 305ms
memory: 56344kb

Pretest #12:

score: 5
Accepted
time: 286ms
memory: 54460kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 25ms
memory: 15040kb

Pretest #19:

score: 5
Accepted
time: 406ms
memory: 54668kb

Pretest #20:

score: 5
Accepted
time: 393ms
memory: 58560kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 299ms
memory: 55036kb

Test #12:

score: 5
Accepted
time: 271ms
memory: 51260kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 361ms
memory: 54028kb

Test #20:

score: 5
Accepted
time: 395ms
memory: 58780kb

Extra Test:

score: 0
Extra Test Passed