QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#604288#9155. 集合Sai_tqwq100 ✓302ms25640kbC++141.2kb2024-10-02 08:49:262024-10-02 08:49:26

Judging History

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

  • [2024-10-02 08:49:26]
  • 评测
  • 测评结果:100
  • 用时:302ms
  • 内存:25640kb
  • [2024-10-02 08:49:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define double long double
#define endl '\n'
mt19937 rnd(time(NULL));
int qpow(int a,int b,int res=1){
	while(b){if(b&1)res=res*a;a=a*a;b>>=1;}
	return res;
}
int n,m,q,a[200009][3],b[200009][3],mxr[200009];
int sa[600009],sb[600009];
int h1[200009],sd,sd2,sd3,ta,tb;
int h2(int x){return (sd*x<<10)^x^sd2^sd3;}
void insert(int x,int f){
	for(int i=0;i<3;i++){
		ta-=h2(sa[a[x][i]]);
		sa[a[x][i]]+=f*h1[x];
		ta+=h2(sa[a[x][i]]);
		tb-=h2(sb[b[x][i]]);
		sb[b[x][i]]+=f*h1[x];
		tb+=h2(sb[b[x][i]]);
	}
}
signed main(){
//	freopen("set.in","r",stdin);
//	freopen("set.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	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;i<=n;i++)mxr[i]=n;
	for(int p=0;p<20;p++){
		sd=rnd();sd2=rnd();sd3=rnd();for(int i=1;i<=n;i++)h1[i]=rnd();ta=tb=0;
		for(int i=1,j=0;i<=n;insert(i++,-1)){
			while(j<=n&&ta==tb)insert(++j,1);
			mxr[i]=min(mxr[i],j-1);
		}
	}
	while(q--){int l,r;cin>>l>>r;cout<<(mxr[l]>=r?"Yes\n":"No\n");}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 157ms
memory: 17180kb

Pretest #12:

score: 5
Accepted
time: 159ms
memory: 17324kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 93ms
memory: 9896kb

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 266ms
memory: 19416kb

Pretest #20:

score: 5
Accepted
time: 302ms
memory: 25604kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 163ms
memory: 16956kb

Test #12:

score: 5
Accepted
time: 154ms
memory: 17416kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 93ms
memory: 9876kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 257ms
memory: 19452kb

Test #20:

score: 5
Accepted
time: 296ms
memory: 25640kb

Extra Test:

score: 0
Extra Test Passed