QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#499507 | #9155. 集合 | eastcloud# | 100 ✓ | 455ms | 112856kb | C++20 | 2.0kb | 2024-07-31 15:03:05 | 2024-07-31 15:03:06 |
Judging History
answer
#include<bits/stdc++.h>
#define ll unsigned long long
#define pi pair<ll,ll>
#define fi first
#define se second
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mem(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define vi vector<ll>
#define arr array
#define pb push_back
#define mp make_pair
using namespace std;
#define N 2000005
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void write(ll x){
if(x<0)x=-x,putchar('-');
if(x/10)write(x/10);
putchar(x%10+'0');
}
ll p[N],a[N][4],b[N][4],val[N];
ll res[N];
vector<pi> Q[N];
unordered_map<ll,ll> t;
ll sum=0,cnt=0;
mt19937_64 rnd(114514);
void add(ll v,ll pos){cnt++;
if(t[val[v]]==1)sum--;
if(t[val[v]]==0)sum++;
t[val[v]]--;
val[v]^=p[pos];
t[val[v]]++;
if(t[val[v]]==0)sum--;
if(t[val[v]]==1)sum++;
}
void del(ll v,ll pos){cnt++;
if(t[val[v]]==0)sum++;
if(t[val[v]]==-1)sum--;
t[val[v]]++;
val[v]^=p[pos];
t[val[v]]--;
if(t[val[v]]==0)sum--;
if(t[val[v]]==-1)sum++;
}
int main(){
#ifdef EAST_CLOUD
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
ll n=read(),m=read(),q=read();
for(ll i=1;i<=n;i++)p[i]=rnd();
for(ll i=1;i<=n;i++)for(ll j=1;j<=3;j++)a[i][j]=read();
for(ll i=1;i<=n;i++)for(ll j=1;j<=3;j++)b[i][j]=read();
for(ll i=1;i<=q;i++){
ll l=read(),r=read();
Q[r].push_back(mp(i,l));
}
ll l=1;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=3;j++)add(a[i][j],i),del(b[i][j]+m,i);
while(sum!=0){
for(ll j=1;j<=3;j++)add(a[l][j],l),del(b[l][j]+m,l);
l++;
}
if(clock()*1.0/CLOCKS_PER_SEC*1000>900){assert(l<=i);break;}
for(auto [id,L]:Q[i])if(L>=l)res[id]=1;
}
for(ll i=1;i<=q;i++){
if(res[i])printf("Yes\n");
else printf("No\n");
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 12108kb
Pretest #2:
score: 5
Accepted
time: 3ms
memory: 11920kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 12112kb
Pretest #4:
score: 5
Accepted
time: 3ms
memory: 12216kb
Pretest #5:
score: 5
Accepted
time: 3ms
memory: 11812kb
Pretest #6:
score: 5
Accepted
time: 3ms
memory: 11924kb
Pretest #7:
score: 5
Accepted
time: 3ms
memory: 12028kb
Pretest #8:
score: 5
Accepted
time: 3ms
memory: 11960kb
Pretest #9:
score: 5
Accepted
time: 11ms
memory: 17916kb
Pretest #10:
score: 5
Accepted
time: 8ms
memory: 15716kb
Pretest #11:
score: 5
Accepted
time: 286ms
memory: 80524kb
Pretest #12:
score: 5
Accepted
time: 279ms
memory: 80324kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 12396kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 14352kb
Pretest #15:
score: 5
Accepted
time: 58ms
memory: 41872kb
Pretest #16:
score: 5
Accepted
time: 74ms
memory: 41924kb
Pretest #17:
score: 5
Accepted
time: 25ms
memory: 18332kb
Pretest #18:
score: 5
Accepted
time: 27ms
memory: 17424kb
Pretest #19:
score: 5
Accepted
time: 441ms
memory: 107692kb
Pretest #20:
score: 5
Accepted
time: 455ms
memory: 108472kb
Final Tests
Test #1:
score: 5
Accepted
time: 4ms
memory: 12004kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 12144kb
Test #3:
score: 5
Accepted
time: 3ms
memory: 12144kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 11948kb
Test #5:
score: 5
Accepted
time: 3ms
memory: 11948kb
Test #6:
score: 5
Accepted
time: 3ms
memory: 13900kb
Test #7:
score: 5
Accepted
time: 3ms
memory: 12148kb
Test #8:
score: 5
Accepted
time: 3ms
memory: 11960kb
Test #9:
score: 5
Accepted
time: 11ms
memory: 18012kb
Test #10:
score: 5
Accepted
time: 16ms
memory: 18124kb
Test #11:
score: 5
Accepted
time: 273ms
memory: 78504kb
Test #12:
score: 5
Accepted
time: 279ms
memory: 78424kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 12460kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 12500kb
Test #15:
score: 5
Accepted
time: 64ms
memory: 42100kb
Test #16:
score: 5
Accepted
time: 60ms
memory: 43908kb
Test #17:
score: 5
Accepted
time: 24ms
memory: 18528kb
Test #18:
score: 5
Accepted
time: 19ms
memory: 19324kb
Test #19:
score: 5
Accepted
time: 450ms
memory: 104468kb
Test #20:
score: 5
Accepted
time: 429ms
memory: 112856kb
Extra Test:
score: 0
Extra Test Passed