QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491839#9155. 集合usada_pekora100 ✓492ms65932kbC++141.3kb2024-07-25 23:10:202024-07-25 23:10:20

Judging History

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

  • [2024-07-25 23:10:20]
  • 评测
  • 测评结果:100
  • 用时:492ms
  • 内存:65932kb
  • [2024-07-25 23:10:20]
  • 提交

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define mkp make_pair
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
template<typename T> inline bool chkmin(T &x, const T &y) {
	return (y < x) && (x = y, true);
}
template<typename T> inline bool chkmax(T &x, const T &y) {
	return (x < y) && (x = y, true);
}
constexpr int N = 1e6 + 5;
int n, m, q, a[N][3], b[N][3], p[N], tot;
ull A[N], B[N], rd[N];
mt19937 rng(1u * time(NULL));
inline void ins(ull x, int opt) {
	static unordered_map<ull, int> cnt;
	if (cnt[x] != 0)
		tot--;
	if ((cnt[x] += opt) != 0)
		tot++;
}
inline void work(int i) {
	for (int j = 0; j < 3; j++) {
		ins(A[a[i][j]], -1), A[a[i][j]] ^= rd[i], ins(A[a[i][j]], 1);
		ins(B[b[i][j]], 1), B[b[i][j]] ^= rd[i], ins(B[b[i][j]], -1);
	}
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++)
			cin >> b[i][j];
	for (int i = 1; i <= n; i++)
		rd[i] = rng();
	for (int l = 1, r = 0; l <= n; l++) {
		while (r <= n && tot == 0)
			work(++r);
		p[l] = r;
		work(l);
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		cout << ((p[l] > r) ? "Yes\n" : "No\n");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 356ms
memory: 61936kb

Pretest #12:

score: 5
Accepted
time: 386ms
memory: 57152kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 491ms
memory: 60324kb

Pretest #20:

score: 5
Accepted
time: 478ms
memory: 65932kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 377ms
memory: 60064kb

Test #12:

score: 5
Accepted
time: 352ms
memory: 57756kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 96ms
memory: 8208kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 492ms
memory: 59412kb

Test #20:

score: 5
Accepted
time: 461ms
memory: 63364kb

Extra Test:

score: 0
Extra Test Passed