QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498372#9155. 集合biuld#100 ✓432ms19316kbC++141.8kb2024-07-30 12:55:132024-07-30 12:55:14

Judging History

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

  • [2024-07-30 12:55:14]
  • 评测
  • 测评结果:100
  • 用时:432ms
  • 内存:19316kb
  • [2024-07-30 12:55:13]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 2e5;
const int M = 6e5;

int n, m, q;
struct node{
	int s[3];
}a[N + 5], b[N + 5];

int w[N + 5];

ll ha[M + 5], hb[M + 5];

ull suma, sumb;
inline void update(int x, int f){
	for(int i = 0; i < 3; ++ i){
		// suma -= ha[a[x].s[i]] * ha[a[x].s[i]];
		suma -= ha[a[x].s[i]] * ha[a[x].s[i]] * ha[a[x].s[i]];
		ha[a[x].s[i]] = ha[a[x].s[i]] + f * w[x];
		// cout << a[x].s[i] << ": " << ha[a[x].s[i]] << '\n';
		// suma += ha[a[x].s[i]] * ha[a[x].s[i]];
		suma += ha[a[x].s[i]] * ha[a[x].s[i]] * ha[a[x].s[i]];
		// cout << suma << '\n';
		
		// sumb -= hb[b[x].s[i]] * hb[b[x].s[i]];
		sumb -= hb[b[x].s[i]] * hb[b[x].s[i]] * hb[b[x].s[i]];
		hb[b[x].s[i]] = hb[b[x].s[i]] + f * w[x];
		// cout << b[x].s[i] << ": " << hb[b[x].s[i]] << '\n';
		// sumb += hb[b[x].s[i]] * hb[b[x].s[i]];
		sumb += hb[b[x].s[i]] * hb[b[x].s[i]] * hb[b[x].s[i]];
	}
}

int r[N + 5];
int x, y;

int main(){
	// freopen("a.out", "w", stdout);

	ios::sync_with_stdio(false);

	cin >> n >> m >> q;
	for(int i = 1; i <= n; ++ i) cin >> a[i].s[0] >> a[i].s[1] >> a[i].s[2];
	for(int i = 1; i <= n; ++ i) cin >> b[i].s[0] >> b[i].s[1] >> b[i].s[2];
	
	for(int i = 1; i <= n; ++ i) w[i] = rand();
	// for(int i = 1; i <= n; ++ i) cout << w[i] << ' '; cout << '\n';

	int j = 0;
	for(int i = 1; i <= n; ++ i){
		// cout << i << ":\n";
		// cout << suma << ' ' << sumb << '\n';
		while(j < i || (j < n && suma == sumb)) update(++ j, 1);
		r[i] = suma == sumb ? j : j - 1;
		update(i, -1);
	}

	// for(int i = 1; i <= n; ++ i){
	// 	cout << i << ' ' << r[i] << '\n';
	// }

	while(q --){
		cin >> x >> y;
		cout << (r[x] >= y ? "Yes\n" : "No\n");
	}

	return 0;
}
/*
双指针
判断集合相等
*/

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 72ms
memory: 9772kb

Pretest #10:

score: 5
Accepted
time: 51ms
memory: 7724kb

Pretest #11:

score: 5
Accepted
time: 108ms
memory: 11276kb

Pretest #12:

score: 5
Accepted
time: 145ms
memory: 10952kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 280ms
memory: 7804kb

Pretest #16:

score: 5
Accepted
time: 276ms
memory: 7764kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 9ms
memory: 10808kb

Pretest #19:

score: 5
Accepted
time: 432ms
memory: 10684kb

Pretest #20:

score: 5
Accepted
time: 423ms
memory: 19316kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 47ms
memory: 7744kb

Test #10:

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

Test #11:

score: 5
Accepted
time: 91ms
memory: 11364kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 363ms
memory: 7852kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 407ms
memory: 10736kb

Test #20:

score: 5
Accepted
time: 383ms
memory: 19272kb

Extra Test:

score: 0
Extra Test Passed