QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489435 | #9155. 集合 | clly | 100 ✓ | 264ms | 28664kb | C++14 | 1.5kb | 2024-07-24 20:07:53 | 2024-07-24 20:07:54 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld double
using namespace std;
const ll N=2e5+100,M=6e5+100;
inline ll read();
ll a[N][3],b[N][3],mp[M],R[N],msk,q,n,m,T;
ull s1,s2,ap[M],bp[M];
ull rd(ull x)
{
x=x;
x=x*1331;
x=x^msk;
x=x*13;
x=x^msk;
x=x*131;
return x;
}
void add(ll x,ll w)
{
for(int i=0;i<=2;i++)
{
s1=s1-rd(ap[a[x][i]]);
ap[a[x][i]]=ap[a[x][i]]+w*mp[x];
s1=s1+rd(ap[a[x][i]]);
}
for(int i=0;i<=2;i++)
{
s2=s2-rd(bp[b[x][i]]);
bp[b[x][i]]=bp[b[x][i]]+w*mp[x];
s2=s2+rd(bp[b[x][i]]);
}
}
void solve()
{
s1=0,s2=0;
msk=rand();
for(int i=1;i<=n;i++)
{
mp[i]=rand()*rand()+rand();
}
for(int i=1;i<=m;i++)
ap[i]=bp[i]=0;
add(1,1);
for(int i=1,j=0;i<=n;add(i,-1),i++)
{
while(s1==s2&&j<n)
{
j++;
add(j+1,1);
}
R[i]=min(R[i],(ll)j);
}
return ;
}
int main()
{
srand(20090302);
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)
for(int j=0;j<=2;j++) a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=0;j<=2;j++) b[i][j]=read();
for(int i=1;i<=n;i++) R[i]=n;
T=15;
while(T--)
solve();
ll l,r;
while(q--)
{
l=read(),r=read();
if(r<=R[l]) printf("Yes\n");
else printf("No\n");
}
return 0;
}
inline ll read()
{
ll w=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=w*10+c-'0';
c=getchar();
}
return w*f;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 13916kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 14028kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 13992kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 13900kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 13968kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 13920kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 13904kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 13912kb
Pretest #9:
score: 5
Accepted
time: 12ms
memory: 13904kb
Pretest #10:
score: 5
Accepted
time: 8ms
memory: 13928kb
Pretest #11:
score: 5
Accepted
time: 168ms
memory: 23008kb
Pretest #12:
score: 5
Accepted
time: 161ms
memory: 19452kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 16040kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 13956kb
Pretest #15:
score: 5
Accepted
time: 54ms
memory: 13996kb
Pretest #16:
score: 5
Accepted
time: 55ms
memory: 14036kb
Pretest #17:
score: 5
Accepted
time: 13ms
memory: 13908kb
Pretest #18:
score: 5
Accepted
time: 20ms
memory: 16480kb
Pretest #19:
score: 5
Accepted
time: 228ms
memory: 19748kb
Pretest #20:
score: 0
Wrong Answer
time: 264ms
memory: 28664kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 13972kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 13972kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 13920kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 13908kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 13908kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 11880kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 11944kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 13932kb
Test #9:
score: 5
Accepted
time: 11ms
memory: 11872kb
Test #10:
score: 5
Accepted
time: 11ms
memory: 11880kb
Test #11:
score: 5
Accepted
time: 165ms
memory: 20312kb
Test #12:
score: 5
Accepted
time: 162ms
memory: 21248kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 12008kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 14020kb
Test #15:
score: 5
Accepted
time: 50ms
memory: 13932kb
Test #16:
score: 5
Accepted
time: 46ms
memory: 12052kb
Test #17:
score: 5
Accepted
time: 14ms
memory: 11872kb
Test #18:
score: 5
Accepted
time: 20ms
memory: 16488kb
Test #19:
score: 5
Accepted
time: 228ms
memory: 22620kb
Test #20:
score: 5
Accepted
time: 264ms
memory: 26552kb