QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491752 | #9155. 集合 | Gaode_Sean | 100 ✓ | 400ms | 59272kb | C++17 | 1.6kb | 2024-07-25 21:47:46 | 2024-07-25 21:47:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=6e5+5;
int n,m,q;
int a[N][4],b[N][4],mx[N];
ll res;
ll w[N],rs[5],ca[M][5],cb[M][5],mod[5]={0,998244353,1000000001,1000000003,1000000007};
void add_a(int pos,int x,ll val)
{
for(int i=1;i<=4;i++)
{
rs[i]=(rs[i]-ca[a[pos][x]][i]*ca[a[pos][x]][i]%mod[i]*ca[a[pos][x]][i]%mod[i]+mod[i])%mod[i];
ca[a[pos][x]][i]=(ca[a[pos][x]][i]+val*w[pos]+mod[i])%mod[i];
rs[i]=(rs[i]+ca[a[pos][x]][i]*ca[a[pos][x]][i]%mod[i]*ca[a[pos][x]][i]%mod[i]+mod[i])%mod[i];
}
res=0;
for(int i=1;i<=4;i++) res+=rs[i];
}
void add_b(int pos,int x,ll val)
{
for(int i=1;i<=4;i++)
{
rs[i]=(rs[i]+cb[b[pos][x]][i]*cb[b[pos][x]][i]%mod[i]*cb[b[pos][x]][i]%mod[i]+mod[i])%mod[i];
cb[b[pos][x]][i]=(cb[b[pos][x]][i]+val*w[pos]+mod[i])%mod[i];
rs[i]=(rs[i]-cb[b[pos][x]][i]*cb[b[pos][x]][i]%mod[i]*cb[b[pos][x]][i]%mod[i]+mod[i])%mod[i];
}
res=0;
for(int i=1;i<=4;i++) res+=rs[i];
}
void calc(int pos,int val)
{
for(int i=1;i<=3;i++) add_a(pos,i,val),add_b(pos,i,val);
}
int rando(){return (1ll*rand()*rand()+1ll*rand()*rand()*rand())%998244353;}
int main()
{
scanf("%d%d%d",&n,&m,&q),srand((unsigned)time(0));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++) scanf("%d",&a[i][j]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++) scanf("%d",&b[i][j]);
}
for(int i=1;i<=n;i++) w[i]=rando();
for(int l=1,r=0;l<=n;l++)
{
for(;r<=n&&!res;calc(++r,1));
mx[l]=r-1,calc(l,-1);
}
for(int i=1,l,r;i<=q;i++) scanf("%d%d",&l,&r),puts(mx[l]>=r?"Yes":"No");
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 10008kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 9900kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9900kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 9936kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9996kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 9900kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 10032kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9936kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 9880kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 10032kb
Pretest #11:
score: 5
Accepted
time: 275ms
memory: 12792kb
Pretest #12:
score: 5
Accepted
time: 273ms
memory: 13596kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 9836kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 10480kb
Pretest #15:
score: 5
Accepted
time: 102ms
memory: 9892kb
Pretest #16:
score: 5
Accepted
time: 103ms
memory: 12356kb
Pretest #17:
score: 5
Accepted
time: 23ms
memory: 10020kb
Pretest #18:
score: 5
Accepted
time: 27ms
memory: 14528kb
Pretest #19:
score: 5
Accepted
time: 375ms
memory: 13892kb
Pretest #20:
score: 5
Accepted
time: 400ms
memory: 59272kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 10032kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 9964kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9820kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 10028kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 9820kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9880kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 9944kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9884kb
Test #9:
score: 5
Accepted
time: 16ms
memory: 9880kb
Test #10:
score: 5
Accepted
time: 17ms
memory: 10008kb
Test #11:
score: 5
Accepted
time: 265ms
memory: 12724kb
Test #12:
score: 5
Accepted
time: 273ms
memory: 13908kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 9820kb
Test #14:
score: 5
Accepted
time: 5ms
memory: 12548kb
Test #15:
score: 5
Accepted
time: 102ms
memory: 9896kb
Test #16:
score: 5
Accepted
time: 104ms
memory: 10424kb
Test #17:
score: 5
Accepted
time: 23ms
memory: 9968kb
Test #18:
score: 5
Accepted
time: 27ms
memory: 16688kb
Test #19:
score: 5
Accepted
time: 383ms
memory: 14012kb
Test #20:
score: 5
Accepted
time: 392ms
memory: 59192kb
Extra Test:
score: 0
Extra Test Passed