QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490132 | #9155. 集合 | staring# | 100 ✓ | 200ms | 20332kb | C++23 | 2.3kb | 2024-07-25 11:40:05 | 2024-07-25 11:40:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
constexpr int N=2e5+5,M=6e5+5;
constexpr int MOD1=1e9+7,MOD2=1e9+9;
int a[N][3],b[N][3];
int ahash1[M],ahash2[M];
int bhash1[M],bhash2[M];
int pow1[N],pow2[N];
int rightp[N];
void mod1(int& a,int b){a+=b,a>=MOD1?a-=MOD1:0;}
void mod2(int& a,int b){a+=b,a>=MOD2?a-=MOD2:0;}
void add(int i)
{
mod1(ahash1[a[i][0]],pow1[i]),mod1(ahash1[a[i][1]],pow1[i]),mod1(ahash1[a[i][2]],pow1[i]);
mod2(ahash2[a[i][0]],pow2[i]),mod2(ahash2[a[i][1]],pow2[i]),mod2(ahash2[a[i][2]],pow2[i]);
mod1(bhash1[b[i][0]],pow1[i]),mod1(bhash1[b[i][1]],pow1[i]),mod1(bhash1[b[i][2]],pow1[i]);
mod2(bhash2[b[i][0]],pow2[i]),mod2(bhash2[b[i][1]],pow2[i]),mod2(bhash2[b[i][2]],pow2[i]);
}
void del(int i)
{
mod1(ahash1[a[i][0]],MOD1-pow1[i]),mod1(ahash1[a[i][1]],MOD1-pow1[i]),mod1(ahash1[a[i][2]],MOD1-pow1[i]);
mod2(ahash2[a[i][0]],MOD2-pow2[i]),mod2(ahash2[a[i][1]],MOD2-pow2[i]),mod2(ahash2[a[i][2]],MOD2-pow2[i]);
mod1(bhash1[b[i][0]],MOD1-pow1[i]),mod1(bhash1[b[i][1]],MOD1-pow1[i]),mod1(bhash1[b[i][2]],MOD1-pow1[i]);
mod2(bhash2[b[i][0]],MOD2-pow2[i]),mod2(bhash2[b[i][1]],MOD2-pow2[i]),mod2(bhash2[b[i][2]],MOD2-pow2[i]);
}
int check(int i)
{
vector<PII> va{{ahash1[a[i][0]],ahash2[a[i][0]]},{ahash1[a[i][1]],ahash2[a[i][1]]},{ahash1[a[i][2]],ahash2[a[i][2]]}};
vector<PII> vb{{bhash1[b[i][0]],bhash2[b[i][0]]},{bhash1[b[i][1]],bhash2[b[i][1]]},{bhash1[b[i][2]],bhash2[b[i][2]]}};
sort(va.begin(),va.end()),sort(vb.begin(),vb.end());
return va[0]==vb[0]&&va[1]==vb[1]&&va[2]==vb[2];
}
int main()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
for(int i=1;i<=n;i++)scanf("%d%d%d",&b[i][0],&b[i][1],&b[i][2]);
pow1[0]=pow2[0]=1;
for(int i=1;i<=n;i++)pow1[i]=pow1[i-1]<<1,pow1[i]>=MOD1?pow1[i]-=MOD1:0,pow2[i]=pow2[i-1]<<1,pow2[i]>=MOD2?pow2[i]-=MOD2:0;
for(int i=1,j=0;i<=n;i++)
{
do add(++j);while(j<=n&&check(j));
del(i),del(j),rightp[i]=--j;
}
for(int i=1;i<=n;i++)rightp[i]=max(rightp[i],rightp[i-1]);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
puts(rightp[l]>=r?"Yes":"No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 7780kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 10056kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 10056kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9860kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9800kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 7824kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9828kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 7828kb
Pretest #9:
score: 5
Accepted
time: 16ms
memory: 9824kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 10088kb
Pretest #11:
score: 5
Accepted
time: 86ms
memory: 12168kb
Pretest #12:
score: 5
Accepted
time: 90ms
memory: 11932kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 10092kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 7880kb
Pretest #15:
score: 5
Accepted
time: 101ms
memory: 9824kb
Pretest #16:
score: 5
Accepted
time: 106ms
memory: 10172kb
Pretest #17:
score: 5
Accepted
time: 4ms
memory: 12016kb
Pretest #18:
score: 5
Accepted
time: 9ms
memory: 10680kb
Pretest #19:
score: 5
Accepted
time: 200ms
memory: 12148kb
Pretest #20:
score: 5
Accepted
time: 199ms
memory: 20068kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 10056kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 9828kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9756kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9760kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9828kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9800kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9824kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 7768kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 9824kb
Test #10:
score: 5
Accepted
time: 16ms
memory: 9824kb
Test #11:
score: 5
Accepted
time: 83ms
memory: 12120kb
Test #12:
score: 5
Accepted
time: 87ms
memory: 11860kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 8040kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 9948kb
Test #15:
score: 5
Accepted
time: 95ms
memory: 10116kb
Test #16:
score: 5
Accepted
time: 107ms
memory: 10172kb
Test #17:
score: 5
Accepted
time: 4ms
memory: 9888kb
Test #18:
score: 5
Accepted
time: 9ms
memory: 10584kb
Test #19:
score: 5
Accepted
time: 194ms
memory: 14000kb
Test #20:
score: 5
Accepted
time: 188ms
memory: 20332kb
Extra Test:
score: 0
Extra Test Passed