QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497995 | #9155. 集合 | Jie_XuSheng# | 100 ✓ | 624ms | 38832kb | C++14 | 2.1kb | 2024-07-29 21:32:52 | 2024-07-29 21:32:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+10,mod=1e9+7,p=1e5+7;
int n,m,q,a[N],b[N],la[N],lb[N],ya[N],yb[N],id[N],x,y,mi[N];
int ksm(int x,int y){
int rt=1;
while(y){
if(y&1) rt=rt*x%mod;
x=x*x%mod;
y>>=1;
}
return rt;
}
int inv(int t){
if(t==0) return 1;
return ksm(t,mod-2);
}
void adda(int pl,int t){
la[t]++;
x=x*inv(ya[t])%mod;
ya[t]=ya[t]*p+pl;
ya[t]%=mod;
x=x*ya[t]%mod;
}
void addb(int pl,int t){
lb[t]++;
y=y*inv(yb[t])%mod;
yb[t]=yb[t]*p+pl;
yb[t]%=mod;
y=y*yb[t]%mod;
}
void dela(int pl,int t){
la[t]--;
// cout<<"t "<<t<<" "<<ya[t]<<" ";
x=x*inv(ya[t])%mod;
ya[t]=ya[t]-mi[la[t]]*pl%mod;
ya[t]=(ya[t]%mod+mod)%mod;
// cout<<ya[t]<<endl;
if(ya[t]!=0) x=x*ya[t]%mod;
}
void delb(int pl,int t){
lb[t]--;
// cout<<"bt "<<t<<" "<<yb[t]<<" ";
y=y*inv(yb[t])%mod;
yb[t]=yb[t]-mi[lb[t]]*pl%mod;
yb[t]=(yb[t]%mod+mod)%mod;
// cout<<yb[t]<<endl;
if(yb[t]!=0) y=y*yb[t]%mod;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
mi[0]=1;
for(int i=1;i<=n;i++) mi[i]=mi[i-1]*p%mod;
// for(int i=0;i<=m;i++) ya[i]=yb[i]=1;
x=y=1;
for(int i=1;i<=3*n;i++){
cin>>a[i];
}
for(int i=1;i<=3*n;i++){
cin>>b[i];
}
int l=1,r=0;
while(l<=n){
int fl=0;
while(r<=n){
r++;
if(r==n+1){
for(int j=l;j<=n;j++){
id[j]=n+1;
}
fl=1;
break;
}
adda(r,a[r*3-2]);
adda(r,a[r*3-1]);
adda(r,a[r*3]);
addb(r,b[r*3-2]);
addb(r,b[r*3-1]);
addb(r,b[r*3]);
// cout<<"xy "<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
if(x==y) continue;
else{
id[l]=r;
break;
}
}
if(fl==1) break;
while(l<=r){
dela(l,a[l*3-2]);
dela(l,a[l*3-1]);
dela(l,a[l*3]);
delb(l,b[l*3-2]);
delb(l,b[l*3-1]);
delb(l,b[l*3]);
l++;
// cout<<"lr "<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
if(x==y) break;
else{
id[l]=r;
}
}
}
/* for(int i=1;i<=n;i++){
cout<<"id "<<i<<" "<<id[i]<<endl;
}*/
while(q--){
int l,r;
cin>>l>>r;
if(id[l]<=r) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 13832kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 13932kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 13840kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 13904kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 13900kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 13908kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 13980kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 13904kb
Pretest #9:
score: 5
Accepted
time: 80ms
memory: 13892kb
Pretest #10:
score: 5
Accepted
time: 59ms
memory: 13964kb
Pretest #11:
score: 5
Accepted
time: 340ms
memory: 22752kb
Pretest #12:
score: 5
Accepted
time: 342ms
memory: 24784kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 13928kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 13968kb
Pretest #15:
score: 5
Accepted
time: 292ms
memory: 13860kb
Pretest #16:
score: 5
Accepted
time: 248ms
memory: 14036kb
Pretest #17:
score: 5
Accepted
time: 28ms
memory: 14016kb
Pretest #18:
score: 5
Accepted
time: 31ms
memory: 17108kb
Pretest #19:
score: 5
Accepted
time: 613ms
memory: 24752kb
Pretest #20:
score: 5
Accepted
time: 567ms
memory: 38832kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 13900kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 13980kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 13840kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 13960kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 13916kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 13888kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 13820kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 13868kb
Test #9:
score: 5
Accepted
time: 51ms
memory: 13960kb
Test #10:
score: 5
Accepted
time: 71ms
memory: 13924kb
Test #11:
score: 5
Accepted
time: 336ms
memory: 22668kb
Test #12:
score: 5
Accepted
time: 343ms
memory: 24708kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 13864kb
Test #14:
score: 5
Accepted
time: 6ms
memory: 14004kb
Test #15:
score: 5
Accepted
time: 256ms
memory: 13920kb
Test #16:
score: 5
Accepted
time: 259ms
memory: 14072kb
Test #17:
score: 5
Accepted
time: 32ms
memory: 14076kb
Test #18:
score: 5
Accepted
time: 29ms
memory: 17076kb
Test #19:
score: 5
Accepted
time: 587ms
memory: 24876kb
Test #20:
score: 5
Accepted
time: 624ms
memory: 37428kb
Extra Test:
score: 0
Extra Test Passed