QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#616673#9155. 集合SwordDance100 ✓509ms55796kbC++141.1kb2024-10-06 09:57:242024-10-06 09:57:25

Judging History

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

  • [2024-10-06 09:57:25]
  • 评测
  • 测评结果:100
  • 用时:509ms
  • 内存:55796kb
  • [2024-10-06 09:57:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+3,M=6e5+3;
int n,m,q,x,y;
int a[N][3],b[N][3];
int now=1,l[N],cnt;
int val[N],ha1[M],ha2[M];
unordered_map<int,int>mp;
void work(int z,int p){
	if(mp[z]==0) cnt++;
	mp[z]+=p;
	if(mp[z]==0) cnt--;
}
void add(int u){
	for(int i=0;i<3;i++){
		int x=a[u][i];
		work(ha1[x],-1);
    	ha1[x]^=val[u];
    	work(ha1[x],1);
    }
    for(int i=0;i<3;i++){
    	int x=b[u][i];
    	work(ha2[x],1);
    	ha2[x]^=val[u];
    	work(ha2[x],-1);
	}
}
int Main()
{
	srand(time(0));
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++) val[i]=(rand()<<16)+rand();
    for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&b[i][0],&b[i][1],&b[i][2]);
    for(int i=1;i<=n;i++){
    	add(i);
    	while(now<i&&cnt) add(now++);
    	l[i]=now;
	} 
    for(int i=1;i<=q;i++){
    	scanf("%d%d",&x,&y);
    	puts((x>=l[y])?"Yes":"No");
	}
	return 0;
}
int main()
{
	//freopen("set4.in","r",stdin);
    int Case=1;
    while(Case--) Main();
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 391ms
memory: 55796kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 95ms
memory: 10252kb

Pretest #16:

score: 5
Accepted
time: 101ms
memory: 10292kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 22ms
memory: 14660kb

Pretest #19:

score: 5
Accepted
time: 509ms
memory: 54356kb

Pretest #20:

score: 5
Accepted
time: 465ms
memory: 53328kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 373ms
memory: 52512kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

score: 5
Accepted
time: 14ms
memory: 14628kb

Test #19:

score: 5
Accepted
time: 442ms
memory: 53452kb

Test #20:

score: 5
Accepted
time: 501ms
memory: 53404kb

Extra Test:

score: 0
Extra Test Passed