QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526886#9155. 集合_LSA_100 ✓507ms80840kbC++141.9kb2024-08-22 00:09:142024-08-22 00:09:14

Judging History

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

  • [2024-08-22 00:09:14]
  • 评测
  • 测评结果:100
  • 用时:507ms
  • 内存:80840kb
  • [2024-08-22 00:09:14]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
ll read(){
	ll X = 0,r = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-') ch = getchar();
	if(ch == '-') r = -1,ch = getchar();
	while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
	return X*r;
}
const int N = 2e5+10;
const int M = 6e5+10;
int n,m,q;
int a[N][3],b[N][3];
ull P = 13131;
ull val[N],pw[N];
mt19937_64 rnd(time(0));
vector<pii> v[N];
bool ans[1010100];
unordered_map<ull,int> mp;
int cnt;
ull hsh[M][2];
bool add(int x,int y){
	for(int k=0;k<=2;k++){
		if(mp[hsh[a[x][k]][0]] == 1) cnt--;
		mp[hsh[a[x][k]][0]]--;
		if(mp[hsh[a[x][k]][0]] == -1) cnt++;
		hsh[a[x][k]][0] += val[x]*pw[x]*y;
		if(mp[hsh[a[x][k]][0]] == -1) cnt--;
		mp[hsh[a[x][k]][0]]++;
		if(mp[hsh[a[x][k]][0]] == 1) cnt++;
	}
	for(int k=0;k<=2;k++){
		if(mp[hsh[b[x][k]][1]] == -1) cnt--;
		mp[hsh[b[x][k]][1]]++;
		if(mp[hsh[b[x][k]][1]] == 1) cnt++;
		hsh[b[x][k]][1] += val[x]*pw[x]*y;
		if(mp[hsh[b[x][k]][1]] == 1) cnt--;
		mp[hsh[b[x][k]][1]]--;
		if(mp[hsh[b[x][k]][1]] == -1) cnt++;
	}
	return (!cnt);
}
signed main(){
	n = read(); m = read(); q = read();
	for(int i=1;i<=n;i++){
		a[i][0] = read();
		a[i][1] = read();
		a[i][2] = read();
	}
	for(int i=1;i<=n;i++){
		b[i][0] = read();
		b[i][1] = read();
		b[i][2] = read();
	}
	for(int i=1;i<=q;i++){
		int l = read(),r = read();
		v[l].push_back(mk(r,i));
	}
	pw[0] = 1;
	for(int i=1;i<=n;i++) pw[i] = pw[i-1]*P;
	for(int i=1;i<=n;i++) val[i] = rnd();
	for(int l=1,r=0;l<=n;l++){
		if(r < l) add(l,1),r = l;
		while(r <= n && add(++r,1));
		if(r <= n) add(r--,-1);
		for(auto it : v[l])
			ans[it.se] = it.fi <= r;
		add(l,-1);
	}
	for(int i=1;i<=q;i++) puts(ans[i] ? "Yes" : "No");
	return 0;
}


Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 12ms
memory: 19780kb

Pretest #10:

score: 5
Accepted
time: 13ms
memory: 17748kb

Pretest #11:

score: 5
Accepted
time: 376ms
memory: 71288kb

Pretest #12:

score: 5
Accepted
time: 371ms
memory: 68560kb

Pretest #13:

score: 5
Accepted
time: 5ms
memory: 16380kb

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 49ms
memory: 27856kb

Pretest #16:

score: 5
Accepted
time: 65ms
memory: 27988kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 458ms
memory: 76236kb

Pretest #20:

score: 5
Accepted
time: 475ms
memory: 80296kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 13ms
memory: 19772kb

Test #10:

score: 5
Accepted
time: 12ms
memory: 17736kb

Test #11:

score: 5
Accepted
time: 357ms
memory: 68624kb

Test #12:

score: 5
Accepted
time: 342ms
memory: 64588kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 48ms
memory: 27860kb

Test #16:

score: 5
Accepted
time: 61ms
memory: 30008kb

Test #17:

score: 5
Accepted
time: 23ms
memory: 20332kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 479ms
memory: 74784kb

Test #20:

score: 5
Accepted
time: 507ms
memory: 80840kb

Extra Test:

score: 0
Extra Test Passed