QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#507144#9155. 集合Others100 ✓194ms40892kbC++142.4kb2024-08-06 11:39:482024-08-06 11:39:48

Judging History

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

  • [2024-08-06 11:39:48]
  • 评测
  • 测评结果:100
  • 用时:194ms
  • 内存:40892kb
  • [2024-08-06 11:39:48]
  • 提交

answer

// LUOGU_RID: 170800470
#include <bits/stdc++.h>
#define ll long long
#define wdnmd const int mod=::mod;
#define lb(i) ((i)&(-(i)))
#define wr(x,ch) write(x),putchar(ch)
using namespace std;
#define gh() getchar()
inline long long read() {
	char ch=gh();
	long long x=0;
	char t=0;
	while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
	return t?-x:x;
}
void write(ll x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) write(x/10);
    putchar(x%10^48);
    return ;
}
const int N=1e6+5,mod1=1e9+9,mod2=1e9+7,mod3=10086001;
int a[N][3],b[N][3],Rig[N],n,m,q;
struct _has {
	int a,b,c;
	bool operator==(const _has &p) const {
		return a==p.a&&b==p.b&&c==p.c;
	}
	_has operator*(const _has &p) const {
		return (_has){1ll*a*p.a%mod1,1ll*b*p.b%mod2,1ll*c*p.c%mod3};
	}
	_has operator+(const _has &p) const {
		return (_has){(a+p.a)%mod1,(b+p.b)%mod2,(c+p.c)%mod3};
	}
	_has operator-(const _has &p) const {
		return (_has){(a-p.a+mod1)%mod1,(b-p.b+mod2)%mod2,(c-p.c+mod3)%mod3};
	}
}hasa,hasb,ha[N],hb[N],base[N],ibase[N];
void ins(int x) {
	for(int i=0;i<3;i++) {
		hasa=hasa-ha[a[x][i]];
		ha[a[x][i]]=ha[a[x][i]]*base[x];
		hasa=hasa+ha[a[x][i]];
		hasb=hasb-hb[b[x][i]];
		hb[b[x][i]]=hb[b[x][i]]*base[x];
		hasb=hasb+hb[b[x][i]];
	}
	return ;
}
void del(int x) {
	for(int i=0;i<3;i++) {
		hasa=hasa-ha[a[x][i]];
		ha[a[x][i]]=ha[a[x][i]]*ibase[x];
		hasa=hasa+ha[a[x][i]];
		hasb=hasb-hb[b[x][i]];
		hb[b[x][i]]=hb[b[x][i]]*ibase[x];
		hasb=hasb+hb[b[x][i]];
	}
	return ;
}
int random(int x) {
	return 1ll*rand()*rand()%x+1;
}
int qpow(int x,int y,const int mod) {
	int ans=1;
	while(y) {
		if(y&1) ans=1ll*ans*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return ans;
}
signed main() {
	srand(114514);
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++) 
		for(int j=0;j<3;j++) a[i][j]=read();
	for(int i=1;i<=n;i++) 
		for(int j=0;j<3;j++) b[i][j]=read();
	for(int i=1;i<=n;i++) base[i]=(_has){random(mod1-1),random(mod2-1),random(mod3-1)};
	for(int i=1;i<=n;i++) ibase[i]=(_has){qpow(base[i].a,mod1-2,mod1),qpow(base[i].b,mod2-2,mod2),qpow(base[i].c,mod3-2,mod3)};
	for(int i=1;i<=m;i++) ha[i]=hb[i]=(_has){1,1,1},hasa=hasa+ha[i],hasb=hasb+hb[i];
	int l=1,r=0;
	while(l<=n) {
		while(r<n&&hasa==hasb) 
			ins(++r);
		Rig[l]=r-1+(hasa==hasb);
		del(l++);
	}
	while(q--) {
		l=read(),r=read();
		puts(r<=Rig[l]?"Yes":"No");
	}
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 10ms
memory: 15896kb

Pretest #10:

score: 5
Accepted
time: 7ms
memory: 15892kb

Pretest #11:

score: 5
Accepted
time: 121ms
memory: 28360kb

Pretest #12:

score: 5
Accepted
time: 117ms
memory: 28408kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 44ms
memory: 15936kb

Pretest #16:

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

Pretest #17:

score: 5
Accepted
time: 11ms
memory: 18072kb

Pretest #18:

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

Pretest #19:

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

Pretest #20:

score: 5
Accepted
time: 189ms
memory: 40584kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 10ms
memory: 15964kb

Test #10:

score: 5
Accepted
time: 7ms
memory: 15888kb

Test #11:

score: 5
Accepted
time: 117ms
memory: 26580kb

Test #12:

score: 5
Accepted
time: 121ms
memory: 24772kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 45ms
memory: 16000kb

Test #16:

score: 5
Accepted
time: 40ms
memory: 16000kb

Test #17:

score: 5
Accepted
time: 11ms
memory: 16148kb

Test #18:

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

Test #19:

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

Test #20:

score: 5
Accepted
time: 194ms
memory: 40892kb

Extra Test:

score: 0
Extra Test Passed