QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#495200 | #9155. 集合 | Actuct | 100 ✓ | 401ms | 59200kb | C++14 | 1.6kb | 2024-07-27 19:26:30 | 2024-07-27 19:26:35 |
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: 1ms
memory: 10036kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 9952kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9940kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 10008kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9956kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 10036kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 10028kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9876kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 9844kb
Pretest #10:
score: 5
Accepted
time: 17ms
memory: 9988kb
Pretest #11:
score: 5
Accepted
time: 267ms
memory: 13568kb
Pretest #12:
score: 5
Accepted
time: 263ms
memory: 13324kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 9956kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 10304kb
Pretest #15:
score: 5
Accepted
time: 92ms
memory: 10036kb
Pretest #16:
score: 5
Accepted
time: 93ms
memory: 10436kb
Pretest #17:
score: 5
Accepted
time: 23ms
memory: 9832kb
Pretest #18:
score: 5
Accepted
time: 26ms
memory: 14564kb
Pretest #19:
score: 5
Accepted
time: 373ms
memory: 12920kb
Pretest #20:
score: 5
Accepted
time: 393ms
memory: 59156kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 10000kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 10036kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9960kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 9892kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9940kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 10028kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9900kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 10036kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 9892kb
Test #10:
score: 5
Accepted
time: 13ms
memory: 10008kb
Test #11:
score: 5
Accepted
time: 268ms
memory: 12560kb
Test #12:
score: 5
Accepted
time: 267ms
memory: 13128kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 10044kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 10428kb
Test #15:
score: 5
Accepted
time: 108ms
memory: 9840kb
Test #16:
score: 5
Accepted
time: 96ms
memory: 10308kb
Test #17:
score: 5
Accepted
time: 23ms
memory: 9936kb
Test #18:
score: 5
Accepted
time: 26ms
memory: 14640kb
Test #19:
score: 5
Accepted
time: 382ms
memory: 13824kb
Test #20:
score: 5
Accepted
time: 401ms
memory: 59200kb
Extra Test:
score: 0
Extra Test Passed