QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511244 | #9155. 集合 | Line12 | 100 ✓ | 617ms | 25100kb | C++14 | 1.8kb | 2024-08-09 17:58:48 | 2024-08-09 17:58:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll B1=600007;
const ll P1=998244353;
const ll P2=1000000007;
const int N=600009;
const int M=600009;
int n,m,q,bst[N];
ll s[M],t[M],sum1=1,sum2=1;
struct Set{int x,y,z;} a[N],b[N];
ll ksm(ll a,ll b,ll c){
ll ans=1;
while(b){
if(b&1)ans=ans*a%c;
a=a*a%c;
b>>=1;
}
return ans;
}
ll inv(ll a,ll b){
return ksm(a,b-2,b);
}
void insert1(int x,int i){
sum1=sum1*inv(s[x],P2)%P2;
assert(s[x]%P2!=0);
(s[x]+=ksm(B1,i,P1))%=P1;
sum1=sum1*s[x]%P2;
}
void insert2(int x,int i){
sum2=sum2*inv(t[x],P2)%P2;
assert(t[x]%P2!=0);
(t[x]+=ksm(B1,i,P1))%=P1;
sum2=sum2*t[x]%P2;
}
void delete1(int x,int i){
sum1=sum1*inv(s[x],P2)%P2;
assert(s[x]%P2!=0);
(s[x]=s[x]-ksm(B1,i,P1)+P1)%=P1;
sum1=sum1*s[x]%P2;
}
void delete2(int x,int i){
sum2=sum2*inv(t[x],P2)%P2;
assert(t[x]%P2!=0);
(t[x]=t[x]-ksm(B1,i,P1)+P1)%=P1;
sum2=sum2*t[x]%P2;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
sum1=sum2=1;
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
for(int i=1;i<=n*3;i++)
s[i]=t[i]=1;
int r=0;
for(int l=1;l<=n;l++){
bst[l]=max(bst[l-1],l);
if(sum1==sum2)bst[l]=max(bst[l],r);
while((sum1==sum2||r<l)&&r<=n-1){
r++;
insert1(a[r].x,r);
insert1(a[r].y,r);
insert1(a[r].z,r);
insert2(b[r].x,r);
insert2(b[r].y,r);
insert2(b[r].z,r);
if(sum1!=sum2)break;
bst[l]=r;
}
delete1(a[l].x,l);
delete1(a[l].y,l);
delete1(a[l].z,l);
delete2(b[l].x,l);
delete2(b[l].y,l);
delete2(b[l].z,l);
}
int ql,qr;
for(int i=1;i<=q;i++){
scanf("%d%d",&ql,&qr);
if(bst[ql]>=qr)puts("Yes");
else puts("No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 9872kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 9968kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 9944kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9816kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9964kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9912kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9836kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 9964kb
Pretest #9:
score: 5
Accepted
time: 21ms
memory: 9968kb
Pretest #10:
score: 5
Accepted
time: 22ms
memory: 9776kb
Pretest #11:
score: 5
Accepted
time: 479ms
memory: 22692kb
Pretest #12:
score: 5
Accepted
time: 478ms
memory: 24332kb
Pretest #13:
score: 5
Accepted
time: 6ms
memory: 9968kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 9996kb
Pretest #15:
score: 5
Accepted
time: 116ms
memory: 9808kb
Pretest #16:
score: 5
Accepted
time: 113ms
memory: 9780kb
Pretest #17:
score: 5
Accepted
time: 41ms
memory: 10200kb
Pretest #18:
score: 5
Accepted
time: 46ms
memory: 12192kb
Pretest #19:
score: 5
Accepted
time: 591ms
memory: 22888kb
Pretest #20:
score: 5
Accepted
time: 615ms
memory: 21680kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9952kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 9968kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9972kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9896kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9968kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9828kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9904kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 9776kb
Test #9:
score: 5
Accepted
time: 22ms
memory: 9904kb
Test #10:
score: 5
Accepted
time: 18ms
memory: 9896kb
Test #11:
score: 5
Accepted
time: 483ms
memory: 22840kb
Test #12:
score: 5
Accepted
time: 471ms
memory: 23960kb
Test #13:
score: 5
Accepted
time: 6ms
memory: 9864kb
Test #14:
score: 5
Accepted
time: 6ms
memory: 9944kb
Test #15:
score: 5
Accepted
time: 113ms
memory: 9804kb
Test #16:
score: 5
Accepted
time: 116ms
memory: 9908kb
Test #17:
score: 5
Accepted
time: 45ms
memory: 10088kb
Test #18:
score: 5
Accepted
time: 46ms
memory: 10200kb
Test #19:
score: 5
Accepted
time: 584ms
memory: 25100kb
Test #20:
score: 5
Accepted
time: 617ms
memory: 21868kb
Extra Test:
score: 0
Extra Test Passed