QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502486#9155. 集合Insert_Username_Here100 ✓187ms20840kbC++201.3kb2024-08-03 07:29:152024-08-03 07:29:15

Judging History

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

  • [2024-08-03 07:29:15]
  • 评测
  • 测评结果:100
  • 用时:187ms
  • 内存:20840kb
  • [2024-08-03 07:29:15]
  • 提交

answer

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef array<int, 3> arr;
const ll mod = 1e9 + 7;
// cope counter = 2254

ll rng() {
	static ll x = 123456789, y = 362436069, z = 521288629;
	ll t;
	x ^= x << 16, x ^= x >> 5, x ^= x << 1;
	t = x, x = y, y = z, z = t ^ x ^ y;
	return x ^ y ^ z;
}

const int N = 2e5 + 1;
arr a[N], b[N];
ll bk[N], ans[N], fa[3 * N], fb[3 * N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 0; i < n; i++) for(int j = 0; j < 3; j++) cin >> a[i][j];
	for(int i = 0; i < n; i++) for(int j = 0; j < 3; j++) cin >> b[i][j];
	for(int i = 0; i < n; i++) bk[i] = rng() % mod;
	for(int i = 0; i <= 3 * n; i++) fa[i] = fb[i] = 0;
	int j = 0, l, r;
	int aa[3], bb[3];
	for(int i = 0; i < n; i++) {
		while(j < n) {
			for(int k = 0; k < 3; k++) aa[k] = fa[a[j][k]], bb[k] = fb[b[j][k]];
			sort(aa, aa + 3), sort(bb, bb + 3);
			if(aa[0] != bb[0] || aa[1] != bb[1] || aa[2] != bb[2]) break;
			for(int k = 0; k < 3; k++) fa[a[j][k]] ^= bk[j], fb[b[j][k]] ^= bk[j];
			j++;
		}
		ans[i] = j;
		for(int &k : a[i]) fa[k] ^= bk[i];
		for(int &k : b[i]) fb[k] ^= bk[i];
	}
	for(int i = 0; i < q; i++) {
		cin >> l >> r;
		cout << (ans[l - 1] >= r ? "Yes\n" : "No\n");
	}
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 15ms
memory: 13952kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 62ms
memory: 20756kb

Pretest #12:

score: 5
Accepted
time: 70ms
memory: 20804kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 95ms
memory: 13848kb

Pretest #16:

score: 5
Accepted
time: 92ms
memory: 11948kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 170ms
memory: 20820kb

Pretest #20:

score: 5
Accepted
time: 187ms
memory: 20776kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 62ms
memory: 20836kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

score: 5
Accepted
time: 8ms
memory: 15864kb

Test #18:

score: 5
Accepted
time: 8ms
memory: 14392kb

Test #19:

score: 5
Accepted
time: 164ms
memory: 20832kb

Test #20:

score: 5
Accepted
time: 186ms
memory: 20840kb

Extra Test:

score: 0
Extra Test Passed