QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#526238 | #9155. 集合 | lefy | 100 ✓ | 275ms | 20464kb | C++14 | 1.3kb | 2024-08-21 12:32:57 | 2024-08-21 12:32:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=2e5+10,M=6e5+10;
int a[3][N],b[3][N];
ull to[N],A[M],B[M];
mt19937 rd(time(0));
int pos[N];
int add(int p){
for(int i=0;i<3;i++)A[a[i][p]]+=to[p],B[b[i][p]]+=to[p];
vector<int>t1,t2;
for(int i=0;i<3;i++){
t1.push_back(A[a[i][p]]),t2.push_back(B[b[i][p]]);
// cout<<A[a[i][p]]<<" "<<B[b[i][p]]<<"\n";
}
sort(t1.begin(),t1.end());sort(t2.begin(),t2.end());
for(int i=0;i<3;i++)if(t1[i]^t2[i])return 1;
return 0;
}
void del(int p){
for(int i=0;i<3;i++)A[a[i][p]]-=to[p],B[b[i][p]]-=to[p];
}
int main() {
// freopen("ex_4.in","r",stdin);
// freopen("3.out","w",stdout);
int n,m,Q;scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;i++){
to[i]=rd();
for(int j=0;j<3;j++)scanf("%d",&a[j][i]);
}
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++)scanf("%d",&b[j][i]);
}
for(int i=1,r=0;i<=n;i++){
while(r<n){
r++;
if(r>n)break;
if(add(r)){
del(r);r--;
break;
}
}
pos[i]=r;
del(i);
}
while(Q--){
int l,r;scanf("%d%d",&l,&r);
if(pos[l]>=r)printf("Yes\n");
else printf("No\n");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 14328kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 14016kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 12064kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 14100kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 14080kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 14336kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 14076kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 12068kb
Pretest #9:
score: 5
Accepted
time: 24ms
memory: 14104kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 14108kb
Pretest #11:
score: 5
Accepted
time: 134ms
memory: 13576kb
Pretest #12:
score: 5
Accepted
time: 132ms
memory: 15172kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 11996kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 12036kb
Pretest #15:
score: 5
Accepted
time: 116ms
memory: 14352kb
Pretest #16:
score: 5
Accepted
time: 120ms
memory: 14100kb
Pretest #17:
score: 5
Accepted
time: 10ms
memory: 14124kb
Pretest #18:
score: 5
Accepted
time: 9ms
memory: 14312kb
Pretest #19:
score: 5
Accepted
time: 250ms
memory: 16084kb
Pretest #20:
score: 5
Accepted
time: 275ms
memory: 20240kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 12284kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 14312kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 11968kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 14020kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 12284kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 12256kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 12064kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 12292kb
Test #9:
score: 5
Accepted
time: 25ms
memory: 14016kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 11996kb
Test #11:
score: 5
Accepted
time: 127ms
memory: 16104kb
Test #12:
score: 5
Accepted
time: 122ms
memory: 16100kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 12268kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 12024kb
Test #15:
score: 5
Accepted
time: 116ms
memory: 14304kb
Test #16:
score: 5
Accepted
time: 125ms
memory: 14328kb
Test #17:
score: 5
Accepted
time: 10ms
memory: 12324kb
Test #18:
score: 5
Accepted
time: 14ms
memory: 14648kb
Test #19:
score: 5
Accepted
time: 243ms
memory: 13408kb
Test #20:
score: 5
Accepted
time: 261ms
memory: 20464kb
Extra Test:
score: 0
Extra Test Passed