QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490231#9155. 集合DaiRuiChen007100 ✓540ms20024kbC++171013b2024-07-25 13:15:262024-07-25 13:15:27

Judging History

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

  • [2024-07-25 13:15:27]
  • 评测
  • 测评结果:100
  • 用时:540ms
  • 内存:20024kb
  • [2024-07-25 13:15:26]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
mt19937_64 rnd(time(0));
const int MAXN=2e5+5,MAXM=6e5+5;
int n,m,q,a[MAXN][3],b[MAXN][3],rp[MAXN];
ull hv[MAXN],A[MAXM],B[MAXM];
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	for(int i=1;i<=n;++i) hv[i]=rnd();
	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,j=0;i<=n;++i) {
		while(j<n) {
			vector <ull> mA,mB;
			for(int k:a[j+1]) mA.push_back(A[k]^hv[j+1]),mB.push_back(A[k]);
			for(int k:b[j+1]) mB.push_back(B[k]^hv[j+1]),mA.push_back(B[k]);
			sort(mA.begin(),mA.end()),sort(mB.begin(),mB.end());
			bool flg=1;
			for(int k:{0,1,2,3,4,5}) flg&=(mA[k]==mB[k]);
			if(!flg) break;
			++j;
			for(int k:a[j]) A[k]^=hv[j];
			for(int k:b[j]) B[k]^=hv[j];
		}
		rp[i]=j;
		for(int k:a[i]) A[k]^=hv[i];
		for(int k:b[i]) B[k]^=hv[i];
	}
	for(int l,r;q--;) cin>>l>>r,cout<<(r<=rp[l]?"Yes\n":"No\n");
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 71ms
memory: 9768kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 199ms
memory: 10964kb

Pretest #12:

score: 5
Accepted
time: 208ms
memory: 11584kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 292ms
memory: 9840kb

Pretest #16:

score: 5
Accepted
time: 283ms
memory: 9904kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 412ms
memory: 10816kb

Pretest #20:

score: 5
Accepted
time: 531ms
memory: 20024kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 5
Accepted
time: 183ms
memory: 11196kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 251ms
memory: 12120kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 540ms
memory: 11572kb

Test #20:

score: 5
Accepted
time: 464ms
memory: 20024kb

Extra Test:

score: 0
Extra Test Passed