QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491101#9155. 集合zhenghanyun100 ✓449ms61700kbC++141.7kb2024-07-25 17:14:592024-07-25 17:14:59

Judging History

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

  • [2024-07-25 17:14:59]
  • 评测
  • 测评结果:100
  • 用时:449ms
  • 内存:61700kb
  • [2024-07-25 17:14:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;

mt19937_64 rng(time(NULL));

const int N = 2e5 + 5;
const int M = 6e5 + 5;

int n, m, q, cnt, a[N][3], b[N][3], ans[N];

ll w[N], hsh1[M], hsh2[M];

unordered_map <ll, int> mp;

inline void Add(ll pos, int val) {
	if (mp[pos] == 0) {
		++cnt;
	}
	mp[pos] += val;
	if (mp[pos] == 0) {
		--cnt;
	}
}

inline void add(int i, ll val) {
	Add(hsh1[a[i][0]], -1);
	Add(hsh1[a[i][1]], -1);
	Add(hsh1[a[i][2]], -1);
	hsh1[a[i][0]] += val;
	hsh1[a[i][1]] += val;
	hsh1[a[i][2]] += val;
	Add(hsh1[a[i][0]], 1);
	Add(hsh1[a[i][1]], 1);
	Add(hsh1[a[i][2]], 1);
	Add(hsh2[b[i][0]], 1);
	Add(hsh2[b[i][1]], 1);
	Add(hsh2[b[i][2]], 1);
	hsh2[b[i][0]] += val;
	hsh2[b[i][1]] += val;
	hsh2[b[i][2]] += val;
	Add(hsh2[b[i][0]], -1);
	Add(hsh2[b[i][1]], -1);
	Add(hsh2[b[i][2]], -1);
}

int main() {
//	assert(freopen("set.in", "r", stdin));
//	assert(freopen("set.out", "w", stdout));
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	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];
	}
	for (int i = 1; i <= n; ++i) {
		w[i] = rng();
	}
	for (int i = 1; i <= n; ++i) {
		if (i > 1) {
			add(i - 1, -w[i - 1]);
		}
		ans[i] = ans[i - 1];
		if (ans[i] < i) {
			ans[i] = i;
			add(i, w[i]);
		}
		while (ans[i] < n) {
			add(ans[i] + 1, w[ans[i] + 1]);
			if (cnt != 0) {
				add(ans[i] + 1, -w[ans[i] + 1]);
				break;
			}
			++ans[i];
		}
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (ans[l] >= r) {
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 349ms
memory: 61700kb

Pretest #12:

score: 5
Accepted
time: 327ms
memory: 56192kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 103ms
memory: 10300kb

Pretest #17:

score: 5
Accepted
time: 30ms
memory: 16308kb

Pretest #18:

score: 5
Accepted
time: 29ms
memory: 15020kb

Pretest #19:

score: 5
Accepted
time: 449ms
memory: 56520kb

Pretest #20:

score: 5
Accepted
time: 449ms
memory: 60336kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 5
Accepted
time: 341ms
memory: 54572kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 99ms
memory: 10172kb

Test #16:

score: 5
Accepted
time: 99ms
memory: 10248kb

Test #17:

score: 5
Accepted
time: 26ms
memory: 14284kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 449ms
memory: 54788kb

Test #20:

score: 5
Accepted
time: 444ms
memory: 60720kb

Extra Test:

score: 0
Extra Test Passed