QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#496522 | #9155. 集合 | ucup-team1004 | 100 ✓ | 252ms | 19380kb | C++14 | 1.7kb | 2024-07-28 12:45:02 | 2024-07-28 12:45:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=2e5+10,M=6e5+10;
int n,m,q,a[N][3],b[N][3],ans[N];
void solve(int base,int mod){
static int pw[N],ta[M],tb[M],oa[M],ob[M];
for(int i=pw[0]=1;i<=n;i++)pw[i]=1ll*pw[i-1]*base%mod;
int wa=0,wb=0;
for(int i=n,j=n;i>=1;i--){
for(int k=0;k<3;k++){
ta[a[i][k]]++;
int &w=oa[a[i][k]];
wa=(wa+1ll*(mod-w)*w)%mod;
w=(1ll*w*base+i)%mod;
wa=(wa+1ll*w*w)%mod;
}
for(int k=0;k<3;k++){
tb[b[i][k]]++;
int &w=ob[b[i][k]];
wb=(wb+1ll*(mod-w)*w)%mod;
w=(1ll*w*base+i)%mod;
wb=(wb+1ll*w*w)%mod;
}
for(;j>i&&wa!=wb;j--){
for(int k=0;k<3;k++){
int &w=oa[a[j][k]];
wa=(wa+1ll*(mod-w)*w)%mod;
w=(w+1ll*(mod-pw[--ta[a[j][k]]])*j)%mod;
wa=(wa+1ll*w*w)%mod;
}
for(int k=0;k<3;k++){
int &w=ob[b[j][k]];
wb=(wb+1ll*(mod-w)*w)%mod;
w=(w+1ll*(mod-pw[--tb[b[j][k]]])*j)%mod;
wb=(wb+1ll*w*w)%mod;
}
}
ans[i]=min(ans[i],j);
}
for(int i=1;i<=m;i++){
ta[i]=tb[i]=oa[i]=ob[i]=0;
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++)scanf("%d",&a[i][j]);
}
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++)scanf("%d",&b[i][j]);
}
fill(ans+1,ans+1+n,n);
solve(19260817,1e9+7);
solve(19260817,1e9+9);
solve(19260817,998244353);
for(int l,r;q--;){
scanf("%d%d",&l,&r);
puts(ans[l]>=r?"Yes":"No");
}
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 11956kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 11824kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 11868kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 13992kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 11876kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 11884kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 11860kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 11872kb
Pretest #9:
score: 5
Accepted
time: 21ms
memory: 13876kb
Pretest #10:
score: 5
Accepted
time: 18ms
memory: 14064kb
Pretest #11:
score: 5
Accepted
time: 144ms
memory: 14212kb
Pretest #12:
score: 5
Accepted
time: 140ms
memory: 15044kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 14076kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 14080kb
Pretest #15:
score: 5
Accepted
time: 102ms
memory: 16036kb
Pretest #16:
score: 5
Accepted
time: 100ms
memory: 11868kb
Pretest #17:
score: 5
Accepted
time: 11ms
memory: 14220kb
Pretest #18:
score: 5
Accepted
time: 15ms
memory: 16576kb
Pretest #19:
score: 5
Accepted
time: 250ms
memory: 17216kb
Pretest #20:
score: 5
Accepted
time: 250ms
memory: 19304kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 13872kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 13908kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 15952kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 13908kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 12020kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 13972kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 11808kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 14068kb
Test #9:
score: 5
Accepted
time: 21ms
memory: 12020kb
Test #10:
score: 5
Accepted
time: 18ms
memory: 15972kb
Test #11:
score: 5
Accepted
time: 145ms
memory: 16008kb
Test #12:
score: 5
Accepted
time: 129ms
memory: 14340kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 14000kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 13928kb
Test #15:
score: 5
Accepted
time: 95ms
memory: 13880kb
Test #16:
score: 5
Accepted
time: 102ms
memory: 11948kb
Test #17:
score: 5
Accepted
time: 7ms
memory: 14060kb
Test #18:
score: 5
Accepted
time: 15ms
memory: 14608kb
Test #19:
score: 5
Accepted
time: 245ms
memory: 17272kb
Test #20:
score: 5
Accepted
time: 252ms
memory: 19380kb
Extra Test:
score: 0
Extra Test Passed