QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#507144 | #9155. 集合 | Others | 100 ✓ | 194ms | 40892kb | C++14 | 2.4kb | 2024-08-06 11:39:48 | 2024-08-06 11:39:48 |
Judging History
answer
// LUOGU_RID: 170800470
#include <bits/stdc++.h>
#define ll long long
#define wdnmd const int mod=::mod;
#define lb(i) ((i)&(-(i)))
#define wr(x,ch) write(x),putchar(ch)
using namespace std;
#define gh() getchar()
inline long long read() {
char ch=gh();
long long x=0;
char t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
return t?-x:x;
}
void write(ll x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar(x%10^48);
return ;
}
const int N=1e6+5,mod1=1e9+9,mod2=1e9+7,mod3=10086001;
int a[N][3],b[N][3],Rig[N],n,m,q;
struct _has {
int a,b,c;
bool operator==(const _has &p) const {
return a==p.a&&b==p.b&&c==p.c;
}
_has operator*(const _has &p) const {
return (_has){1ll*a*p.a%mod1,1ll*b*p.b%mod2,1ll*c*p.c%mod3};
}
_has operator+(const _has &p) const {
return (_has){(a+p.a)%mod1,(b+p.b)%mod2,(c+p.c)%mod3};
}
_has operator-(const _has &p) const {
return (_has){(a-p.a+mod1)%mod1,(b-p.b+mod2)%mod2,(c-p.c+mod3)%mod3};
}
}hasa,hasb,ha[N],hb[N],base[N],ibase[N];
void ins(int x) {
for(int i=0;i<3;i++) {
hasa=hasa-ha[a[x][i]];
ha[a[x][i]]=ha[a[x][i]]*base[x];
hasa=hasa+ha[a[x][i]];
hasb=hasb-hb[b[x][i]];
hb[b[x][i]]=hb[b[x][i]]*base[x];
hasb=hasb+hb[b[x][i]];
}
return ;
}
void del(int x) {
for(int i=0;i<3;i++) {
hasa=hasa-ha[a[x][i]];
ha[a[x][i]]=ha[a[x][i]]*ibase[x];
hasa=hasa+ha[a[x][i]];
hasb=hasb-hb[b[x][i]];
hb[b[x][i]]=hb[b[x][i]]*ibase[x];
hasb=hasb+hb[b[x][i]];
}
return ;
}
int random(int x) {
return 1ll*rand()*rand()%x+1;
}
int qpow(int x,int y,const int mod) {
int ans=1;
while(y) {
if(y&1) ans=1ll*ans*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return ans;
}
signed main() {
srand(114514);
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)
for(int j=0;j<3;j++) a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=0;j<3;j++) b[i][j]=read();
for(int i=1;i<=n;i++) base[i]=(_has){random(mod1-1),random(mod2-1),random(mod3-1)};
for(int i=1;i<=n;i++) ibase[i]=(_has){qpow(base[i].a,mod1-2,mod1),qpow(base[i].b,mod2-2,mod2),qpow(base[i].c,mod3-2,mod3)};
for(int i=1;i<=m;i++) ha[i]=hb[i]=(_has){1,1,1},hasa=hasa+ha[i],hasb=hasb+hb[i];
int l=1,r=0;
while(l<=n) {
while(r<n&&hasa==hasb)
ins(++r);
Rig[l]=r-1+(hasa==hasb);
del(l++);
}
while(q--) {
l=read(),r=read();
puts(r<=Rig[l]?"Yes":"No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 15896kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 15892kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 15912kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 15892kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 15904kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 15884kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 15836kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 15888kb
Pretest #9:
score: 5
Accepted
time: 10ms
memory: 15896kb
Pretest #10:
score: 5
Accepted
time: 7ms
memory: 15892kb
Pretest #11:
score: 5
Accepted
time: 121ms
memory: 28360kb
Pretest #12:
score: 5
Accepted
time: 117ms
memory: 28408kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 17968kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 15912kb
Pretest #15:
score: 5
Accepted
time: 44ms
memory: 15936kb
Pretest #16:
score: 5
Accepted
time: 49ms
memory: 15844kb
Pretest #17:
score: 5
Accepted
time: 11ms
memory: 18072kb
Pretest #18:
score: 5
Accepted
time: 15ms
memory: 20288kb
Pretest #19:
score: 5
Accepted
time: 173ms
memory: 27904kb
Pretest #20:
score: 5
Accepted
time: 189ms
memory: 40584kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 15908kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 15920kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 15980kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 15956kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 15852kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 15980kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 15848kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 15856kb
Test #9:
score: 5
Accepted
time: 10ms
memory: 15964kb
Test #10:
score: 5
Accepted
time: 7ms
memory: 15888kb
Test #11:
score: 5
Accepted
time: 117ms
memory: 26580kb
Test #12:
score: 5
Accepted
time: 121ms
memory: 24772kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 16000kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 17968kb
Test #15:
score: 5
Accepted
time: 45ms
memory: 16000kb
Test #16:
score: 5
Accepted
time: 40ms
memory: 16000kb
Test #17:
score: 5
Accepted
time: 11ms
memory: 16148kb
Test #18:
score: 5
Accepted
time: 16ms
memory: 20308kb
Test #19:
score: 5
Accepted
time: 173ms
memory: 28244kb
Test #20:
score: 5
Accepted
time: 194ms
memory: 40892kb
Extra Test:
score: 0
Extra Test Passed