QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490010#9155. 集合Ender32k100 ✓426ms61592kbC++141.8kb2024-07-25 10:15:112024-07-25 10:15:12

Judging History

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

  • [2024-07-25 10:15:12]
  • 评测
  • 测评结果:100
  • 用时:426ms
  • 内存:61592kb
  • [2024-07-25 10:15:11]
  • 提交

answer

// Problem: P10785 [NOI2024] 集合
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10785
// Memory Limit:  MB
// Time Limit:  ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
bool Mbe;

mt19937 rnd(time(0));
const int N = 2e5 + 5;
const int M = 6e5 + 5;

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

ull f[N], pa[M], pb[M], A, B;
unordered_map<ull, ull> h;

ull myr() {
	return ((ull)rnd() << 32) + rnd();
}

ull g(ull x) {
	if (h.find(x) == h.end()) h[x] = myr();
	return h[x];
}

void add(int x, ull op) {
	for (int i = 0; i <= 2; i++) {
		A -= g(pa[a[x][i]]), B -= g(pb[b[x][i]]);
		pa[a[x][i]] += f[x] * op;
		pb[b[x][i]] += f[x] * op;
		A += g(pa[a[x][i]]), B += g(pb[b[x][i]]);
	}
}

void solve() {
	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++) f[i] = myr();
	for (int i = 1, j = 0; i <= n; i++) {
		while (j + 1 <= n && (A == B)) add(++j, 1);
		if (A != B) add(j--, -1);
		res[i] = j, add(i, -1);
	}
	while (q--) {
		int l, r; cin >> l >> r;
		if (res[l] >= r) cout << "Yes\n";
		else cout << "No\n";
	}
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 311ms
memory: 61592kb

Pretest #12:

score: 5
Accepted
time: 270ms
memory: 56716kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 426ms
memory: 56580kb

Pretest #20:

score: 5
Accepted
time: 408ms
memory: 60588kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 304ms
memory: 57492kb

Test #12:

score: 5
Accepted
time: 285ms
memory: 56308kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

score: 5
Accepted
time: 27ms
memory: 16604kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 400ms
memory: 54816kb

Test #20:

score: 5
Accepted
time: 409ms
memory: 60924kb

Extra Test:

score: 0
Extra Test Passed