QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#495197 | #9155. 集合 | eeeel | 100 ✓ | 415ms | 59336kb | C++14 | 1.6kb | 2024-07-27 19:25:21 | 2024-07-27 19:25:21 |
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++)
{
while(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: 10032kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 10032kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9840kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 9872kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 10040kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9880kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9876kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9840kb
Pretest #9:
score: 5
Accepted
time: 17ms
memory: 10032kb
Pretest #10:
score: 5
Accepted
time: 18ms
memory: 9844kb
Pretest #11:
score: 5
Accepted
time: 273ms
memory: 13400kb
Pretest #12:
score: 5
Accepted
time: 264ms
memory: 13480kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 9892kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 10512kb
Pretest #15:
score: 5
Accepted
time: 102ms
memory: 11888kb
Pretest #16:
score: 5
Accepted
time: 106ms
memory: 10424kb
Pretest #17:
score: 5
Accepted
time: 27ms
memory: 9912kb
Pretest #18:
score: 5
Accepted
time: 23ms
memory: 14696kb
Pretest #19:
score: 5
Accepted
time: 370ms
memory: 14112kb
Pretest #20:
score: 5
Accepted
time: 415ms
memory: 59272kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 10016kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 9908kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 10012kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 10036kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 9880kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9956kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 10040kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 10028kb
Test #9:
score: 5
Accepted
time: 17ms
memory: 9956kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 9824kb
Test #11:
score: 5
Accepted
time: 270ms
memory: 13392kb
Test #12:
score: 5
Accepted
time: 269ms
memory: 13804kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 10028kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 10304kb
Test #15:
score: 5
Accepted
time: 103ms
memory: 10012kb
Test #16:
score: 5
Accepted
time: 107ms
memory: 10496kb
Test #17:
score: 5
Accepted
time: 27ms
memory: 9916kb
Test #18:
score: 5
Accepted
time: 27ms
memory: 14500kb
Test #19:
score: 5
Accepted
time: 358ms
memory: 13400kb
Test #20:
score: 5
Accepted
time: 405ms
memory: 59336kb
Extra Test:
score: 0
Extra Test Passed