QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487905#9155. 集合aoliao100 ✓180ms20068kbC++141.2kb2024-07-23 12:03:032024-07-23 12:03:04

Judging History

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

  • [2024-07-23 12:03:04]
  • 评测
  • 测评结果:100
  • 用时:180ms
  • 内存:20068kb
  • [2024-07-23 12:03:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define u64 unsigned long long

const int N = 2e5 + 10, M = 3 * N, P = 13331;
int n, m, q, a[N][3], b[N][3];
u64 p[N], h1[M], h2[M];
int f[N];

int main()
{
	cin >> 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]);
	p[0] = 1;
	for(int i = 1; i <= n; i++) p[i] = p[i - 1] * P;
	
	for(int i = 1, j = 1; i <= n; i++)
	{
		auto check = [&](u64 a1, u64 a2, u64 a3, u64 b1, u64 b2, u64 b3)
		{
			return max({a1,a2,a3}) == max({b1,b2,b3}) && min({a1,a2,a3}) == min({b1,b2,b3}) && a1+a2+a3 == b1+b2+b3;
		};
		
		while(j <= n && check(h1[a[j][0]], h1[a[j][1]], h1[a[j][2]], h2[b[j][0]], h2[b[j][1]], h2[b[j][2]]))
			h1[a[j][0]] += p[j], h1[a[j][1]] += p[j], h1[a[j][2]] += p[j], h2[b[j][0]] += p[j], h2[b[j][1]] += p[j], h2[b[j][2]] += p[j], j++;
		f[i] = j - 1;
		h1[a[i][0]] -= p[i], h1[a[i][1]] -= p[i], h1[a[i][2]] -= p[i], h2[b[i][0]] -= p[i], h2[b[i][1]] -= p[i], h2[b[i][2]] -= p[i];
	}
	
	while(q--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		puts(f[l] >= r ? "Yes" : "No");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 64ms
memory: 11660kb

Pretest #12:

score: 5
Accepted
time: 68ms
memory: 11044kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 161ms
memory: 12596kb

Pretest #20:

score: 5
Accepted
time: 180ms
memory: 20068kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 5
Accepted
time: 67ms
memory: 11600kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 171ms
memory: 12632kb

Test #20:

score: 5
Accepted
time: 179ms
memory: 20008kb

Extra Test:

score: 0
Extra Test Passed