QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492526 | #9155. 集合 | wangziji | 100 ✓ | 783ms | 34968kb | C++20 | 2.7kb | 2024-07-26 13:09:23 | 2024-07-26 13:09:26 |
Judging History
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