QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492526#9155. 集合wangziji100 ✓783ms34968kbC++202.7kb2024-07-26 13:09:232024-07-26 13:09:26

Judging History

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

  • [2024-07-26 13:09:26]
  • 评测
  • 测评结果:100
  • 用时:783ms
  • 内存:34968kb
  • [2024-07-26 13:09:23]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define __int128 int
using namespace std;
mt19937_64 rnd(703651);
struct qwq
{
	int a,b,c;
}a[200005],b[200005];
const int mod=998244353;
int F[200005],R[200005],n,m,q;
int P1=1,P2=1;
int ksm(int x,int y)
{
	x=(x%mod+mod)%mod;
	int rtn=1;
	while(y)
	{
		if(y&1) rtn=(__int128)rtn*x%mod;
		x=(__int128)x*x%mod,y>>=1;
	}
	return rtn;
}
int inv(int x)
{
	return ksm(x,mod-2);
}
struct qaq
{
	int w[600005],s[600005];
	__int128 P1,P2;//int128!
	void init()
	{
		memset(w,0,sizeof w);
		memset(s,0,sizeof s);
		P1=P2=1;
	}
	void ins(qwq X,int i)
	{
		P1=P1*inv(s[X.a]+1)%mod;
		P1=P1*inv(s[X.b]+1)%mod;
		P1=P1*inv(s[X.c]+1)%mod;
		P2=P2*inv(w[X.a]+1)%mod;
		P2=P2*inv(w[X.b]+1)%mod;
		P2=P2*inv(w[X.c]+1)%mod;
		s[X.a]-=w[X.b]+w[X.c];
		s[X.b]-=w[X.a]+w[X.c];
		s[X.c]-=w[X.b]+w[X.a];
		w[X.a]+=F[i];
		w[X.b]+=F[i];
		w[X.c]+=F[i];
		s[X.a]+=w[X.b]+w[X.c];
		s[X.b]+=w[X.a]+w[X.c];
		s[X.c]+=w[X.b]+w[X.a];
		s[X.a]%=mod,w[X.a]%=mod;
		s[X.b]%=mod,w[X.b]%=mod;
		s[X.c]%=mod,w[X.c]%=mod;
		P1=P1*(s[X.a]+1)%mod;
		P1=P1*(s[X.b]+1)%mod;
		P1=P1*(s[X.c]+1)%mod;
		P2=P2*(w[X.a]+1)%mod;
		P2=P2*(w[X.b]+1)%mod;
		P2=P2*(w[X.c]+1)%mod;
		P1=(P1%mod+mod)%mod;
		P2=(P2%mod+mod)%mod;
	}
	void del(qwq X,int i)
	{
		P1=P1*inv(s[X.a]+1)%mod;
		P1=P1*inv(s[X.b]+1)%mod;
		P1=P1*inv(s[X.c]+1)%mod;
		P2=P2*inv(w[X.a]+1)%mod;
		P2=P2*inv(w[X.b]+1)%mod;
		P2=P2*inv(w[X.c]+1)%mod;
		s[X.a]-=w[X.b]+w[X.c];
		s[X.b]-=w[X.a]+w[X.c];
		s[X.c]-=w[X.b]+w[X.a];
		w[X.a]-=F[i];
		w[X.b]-=F[i];
		w[X.c]-=F[i];
		s[X.a]+=w[X.b]+w[X.c];
		s[X.b]+=w[X.a]+w[X.c];
		s[X.c]+=w[X.b]+w[X.a];
		s[X.a]%=mod,w[X.a]%=mod;
		s[X.b]%=mod,w[X.b]%=mod;
		s[X.c]%=mod,w[X.c]%=mod;
		P1=P1*(s[X.a]+1)%mod;
		P1=P1*(s[X.b]+1)%mod;
		P1=P1*(s[X.c]+1)%mod;
		P2=P2*(w[X.a]+1)%mod;
		P2=P2*(w[X.b]+1)%mod;
		P2=P2*(w[X.c]+1)%mod;
		P1=(P1%mod+mod)%mod;
		P2=(P2%mod+mod)%mod;
	}
	void print()
	{
		cout << (int)P1 << " " << (int)P2 << "\n";
	}
}A,B;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	A.init(),B.init();
	cin >> n >> m >> q;
	for(int i=1;i<=n;i++)
		cin >> a[i].a >> a[i].b >> a[i].c;
	for(int i=1;i<=n;i++)
		cin >> b[i].a >> b[i].b >> b[i].c;
	for(int i=1;i<=200000;i++) F[i]=rnd()%mod;
	int rr=0;
	for(int i=1;i<=n;i++)
	{
		//A.init(),B.init(),rr=i-1;
		while(rr<=n&&A.P1==B.P1&&A.P2==B.P2)
		{
			++rr;
			A.ins(a[rr],rr),B.ins(b[rr],rr);
		}
	//	cout << i << " " << rr << " " << (int)A.P1 << " " <<  (int)A.P2 << " " <<  (int)B.P1 << " " <<  (int)B.P2 << "\n";
		A.del(a[i],i),B.del(b[i],i);
		R[i]=rr-1;
	}
	while(q--)
	{
		int l,r;
		cin >> l >> r;
		if(r<=R[l]) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 625ms
memory: 34876kb

Pretest #12:

score: 5
Accepted
time: 620ms
memory: 34840kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 113ms
memory: 27948kb

Pretest #17:

score: 5
Accepted
time: 59ms
memory: 29984kb

Pretest #18:

score: 5
Accepted
time: 69ms
memory: 30312kb

Pretest #19:

score: 5
Accepted
time: 744ms
memory: 34968kb

Pretest #20:

score: 5
Accepted
time: 783ms
memory: 34892kb

Final Tests

Test #1:

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

Test #2:

score: 5
Accepted
time: 6ms
memory: 28028kb

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 5
Accepted
time: 24ms
memory: 27592kb

Test #11:

score: 5
Accepted
time: 618ms
memory: 34824kb

Test #12:

score: 5
Accepted
time: 622ms
memory: 34884kb

Test #13:

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

Test #14:

score: 5
Accepted
time: 8ms
memory: 27732kb

Test #15:

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

Test #16:

score: 5
Accepted
time: 111ms
memory: 29520kb

Test #17:

score: 5
Accepted
time: 63ms
memory: 29716kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 734ms
memory: 34840kb

Test #20:

score: 5
Accepted
time: 781ms
memory: 34840kb

Extra Test:

score: 0
Extra Test Passed