QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489126 | #9155. 集合 | pengyule | 100 ✓ | 858ms | 113832kb | C++14 | 1.8kb | 2024-07-24 18:19:52 | 2024-07-24 18:19:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO {
const int buflen=1<<21;
int x,f;
char ch,buf[buflen],*p1=buf,*p2=buf;
inline char gc(){return p1==p2&&(p2=buf+fread(p1=buf,1,buflen,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
x=0,f=1,ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return f?x:-x;
}
}
using IO::read;
const int N=1e6+5;
const ll base=37,mod=1e9+7;
int n,m,q,a[N][4],b[N][4],lim[N];
ll A[N],B[N],mi[N];
unordered_map<ll,int>S,T;
inline void add(ll &x,ll y){(x+=y)>=mod&&(x-=mod);}
bool Add(int p){
vector<ll>vec;
for(int j=1;j<=3;j++){
S[A[a[p][j]]]--;
vec.emplace_back(A[a[p][j]]);
add(A[a[p][j]],mi[p]);
vec.emplace_back(A[a[p][j]]);
S[A[a[p][j]]]++;
vec.emplace_back(B[b[p][j]]);
T[B[b[p][j]]]--;
add(B[b[p][j]],mi[p]);
vec.emplace_back(B[b[p][j]]);
T[B[b[p][j]]]++;
}
for(ll e:vec){
if(S[e]!=T[e]){
for(int j=3;j>=1;j--){
S[A[a[p][j]]]--;
add(A[a[p][j]],mod-mi[p]);
S[A[a[p][j]]]++;
T[B[b[p][j]]]--;
add(B[b[p][j]],mod-mi[p]);
T[B[b[p][j]]]++;
}
return 0;
}
}
return 1;
}
void Del(int p){
for(int j=1;j<=3;j++){
S[A[a[p][j]]]--;
add(A[a[p][j]],mod-mi[p]);
S[A[a[p][j]]]++;
T[B[b[p][j]]]--;
add(B[b[p][j]],mod-mi[p]);
T[B[b[p][j]]]++;
}
}
int main(){
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)for(int j=1;j<=3;j++)a[i][j]=read();
for(int i=1;i<=n;i++)for(int j=1;j<=3;j++)b[i][j]=read();
mi[0]=1;
for(int i=1;i<=n;i++)mi[i]=mi[i-1]*base%mod;
for(int i=1,j=0;i<=n;i++){
j=max(j,i-1);
while(j<n&&Add(j+1))j++;
lim[i]=j;
Del(i);
}
for(int i=1,l,r;i<=q;i++){
l=read(),r=read();
puts(r<=lim[l]?"Yes":"No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 11820kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 11740kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 11800kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 11992kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 11748kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 11744kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 11892kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 11816kb
Pretest #9:
score: 5
Accepted
time: 3ms
memory: 13464kb
Pretest #10:
score: 5
Accepted
time: 6ms
memory: 11876kb
Pretest #11:
score: 5
Accepted
time: 858ms
memory: 113832kb
Pretest #12:
score: 5
Accepted
time: 826ms
memory: 107496kb
Pretest #13:
score: 5
Accepted
time: 5ms
memory: 12612kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 12568kb
Pretest #15:
score: 5
Accepted
time: 43ms
memory: 12664kb
Pretest #16:
score: 5
Accepted
time: 43ms
memory: 14356kb
Pretest #17:
score: 5
Accepted
time: 38ms
memory: 23076kb
Pretest #18:
score: 5
Accepted
time: 27ms
memory: 21000kb
Pretest #19:
score: 5
Accepted
time: 811ms
memory: 108680kb
Pretest #20:
score: 5
Accepted
time: 763ms
memory: 110580kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 11828kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 11744kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 11808kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 11856kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 11828kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 12040kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 11892kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 11880kb
Test #9:
score: 5
Accepted
time: 9ms
memory: 11880kb
Test #10:
score: 5
Accepted
time: 9ms
memory: 12848kb
Test #11:
score: 5
Accepted
time: 797ms
memory: 112880kb
Test #12:
score: 5
Accepted
time: 735ms
memory: 105224kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 12828kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 12548kb
Test #15:
score: 5
Accepted
time: 38ms
memory: 13448kb
Test #16:
score: 5
Accepted
time: 40ms
memory: 13768kb
Test #17:
score: 5
Accepted
time: 41ms
memory: 21660kb
Test #18:
score: 5
Accepted
time: 36ms
memory: 21256kb
Test #19:
score: 5
Accepted
time: 767ms
memory: 108284kb
Test #20:
score: 5
Accepted
time: 735ms
memory: 109048kb
Extra Test:
score: 0
Extra Test Passed