QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490633#9155. 集合c20230201100 ✓288ms20096kbC++141.2kb2024-07-25 15:55:592024-07-25 15:56:01

Judging History

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

  • [2024-07-25 15:56:01]
  • 评测
  • 测评结果:100
  • 用时:288ms
  • 内存:20096kb
  • [2024-07-25 15:55:59]
  • 提交

answer

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

typedef unsigned long long ull;
const int maxn=2e5+5, maxm=6e5+5;

int a[maxn][3], b[maxn][3], L[maxn];
ull f[maxm], g[maxm], v[maxn];

unordered_map<ull,int> mp;

ull random_x() {
	return 1ull*rand()*rand()*rand()*rand();
}

void add(int i,int o) {
	for(int j=0;j<3;j++) {
		mp[f[a[i][j]]]--;
		if(mp[f[a[i][j]]]==0) mp.erase(f[a[i][j]]);
		mp[g[b[i][j]]]++;
		if(mp[g[b[i][j]]]==0) mp.erase(g[b[i][j]]);
		f[a[i][j]]+= o*v[i];
		g[b[i][j]]+= o*v[i];
		mp[f[a[i][j]]]++;
		if(mp[f[a[i][j]]]==0) mp.erase(f[a[i][j]]);
		mp[g[b[i][j]]]--;
		if(mp[g[b[i][j]]]==0) mp.erase(g[b[i][j]]);
	}
	return ;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	int n,m,q; cin>>n>>m>>q;
	for(int i=1;i<=n;i++) v[i]=random_x();
	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];
	}
	int l=1;
	for(int i=1;i<=n;i++) {
		add(i,1);
		while(l<=i&&mp.size()) add(l++,-1);
		L[i]=l;
	}
	for(int i=1;i<=q;i++) {
		int l,r; cin>>l>>r;
		if(L[r]<=l) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 172ms
memory: 11648kb

Pretest #12:

score: 5
Accepted
time: 173ms
memory: 11836kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 97ms
memory: 9920kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 288ms
memory: 14168kb

Pretest #20:

score: 5
Accepted
time: 284ms
memory: 20068kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 169ms
memory: 11832kb

Test #12:

score: 5
Accepted
time: 167ms
memory: 12108kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

score: 5
Accepted
time: 282ms
memory: 20096kb

Extra Test:

score: 0
Extra Test Passed