QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509120 | #9155. 集合 | jager59 | 100 ✓ | 160ms | 53216kb | C++17 | 2.3kb | 2024-08-08 10:32:24 | 2024-08-08 10:32:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const long long inf=1e13;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
mt19937_64 orz(113132);
int n,m,q,a[N][3],b[N][3],cnt,ans[N];
long long val[N*3][2],vvv[N];
const int mod = 4e6+7;
struct htable{
int head[mod],etot;
struct edge{
int nxt,val;
long long v;
}e[mod];
inline void insert(long long x,int op){
// cerr<<"!"<<x<<' '<<op<<endl;
int p = x%mod;
for(int i = head[p];i;i=e[i].nxt){
if(e[i].v==x){
e[i].val+=op;
if(e[i].val==1&&op==1)cnt++;
else if(e[i].val==-1&&op==-1)cnt++;
else if(!e[i].val)cnt--;
return;
}
}
e[++etot]={head[p],op,x};cnt++;head[p]=etot;
}
}mp;
inline void add(int x,long long v,int op,int k){
if(val[x][op]){
if(op==1)mp.insert(val[x][op],-1);
else mp.insert(val[x][op],1);
}
val[x][op]+=v*k;
if(val[x][op]){
if(op==1)mp.insert(val[x][op],1);
else mp.insert(val[x][op],-1);
}
// cerr<<"??"<<x<<' '<<op<<' '<<val[x][op]<<' '<<cnt<<endl;
}
int main(){
n=read(),m=read(),q=read();
for(int i = 1;i<=n;i++)a[i][0]=read(),a[i][1]=read(),a[i][2]=read(),vvv[i]=orz()%inf+1;
for(int i = 1;i<=n;i++)b[i][0]=read(),b[i][1]=read(),b[i][2]=read();
for(int l = 1,r=0;l<=n;l++){
while(!cnt && r<n){
// cerr<<l<<' '<<r<<endl;
r++;
for(int j = 0;j<3;j++)add(a[r][j],vvv[r],0,1),add(b[r][j],vvv[r],1,1);
// cerr<<l<<' '<<r<<' '<<cnt<<endl;
if(cnt){
// cerr<<l<<' '<<r<<endl;
for(int j = 0;j<3;j++)add(a[r][j],vvv[r],0,-1),add(b[r][j],vvv[r],1,-1);
r--;
break;
}
}
ans[l]=r;
for(int j = 0;j<3;j++)add(a[l][j],vvv[l],0,-1),add(b[l][j],vvv[l],1,-1);
}
while(q--){
int l=read(),r=read();
if(ans[l]>=r)printf("Yes\n");
else printf("No\n");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 10984kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 12912kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 10800kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 12764kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 12776kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 10868kb
Pretest #7:
score: 5
Accepted
time: 3ms
memory: 13584kb
Pretest #8:
score: 5
Accepted
time: 4ms
memory: 15444kb
Pretest #9:
score: 5
Accepted
time: 9ms
memory: 15548kb
Pretest #10:
score: 5
Accepted
time: 14ms
memory: 13596kb
Pretest #11:
score: 5
Accepted
time: 92ms
memory: 51128kb
Pretest #12:
score: 5
Accepted
time: 87ms
memory: 49052kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 24908kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 23932kb
Pretest #15:
score: 5
Accepted
time: 51ms
memory: 29184kb
Pretest #16:
score: 5
Accepted
time: 49ms
memory: 24468kb
Pretest #17:
score: 5
Accepted
time: 8ms
memory: 30632kb
Pretest #18:
score: 5
Accepted
time: 3ms
memory: 31140kb
Pretest #19:
score: 5
Accepted
time: 147ms
memory: 47008kb
Pretest #20:
score: 5
Accepted
time: 160ms
memory: 51168kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 10776kb
Test #2:
score: 5
Accepted
time: 3ms
memory: 12796kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 12892kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 10804kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 10748kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 12716kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 13696kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 13100kb
Test #9:
score: 5
Accepted
time: 9ms
memory: 13936kb
Test #10:
score: 5
Accepted
time: 10ms
memory: 15644kb
Test #11:
score: 5
Accepted
time: 89ms
memory: 49080kb
Test #12:
score: 5
Accepted
time: 81ms
memory: 47028kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 26896kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 24132kb
Test #15:
score: 5
Accepted
time: 49ms
memory: 26964kb
Test #16:
score: 5
Accepted
time: 53ms
memory: 24380kb
Test #17:
score: 5
Accepted
time: 12ms
memory: 28924kb
Test #18:
score: 5
Accepted
time: 12ms
memory: 27832kb
Test #19:
score: 5
Accepted
time: 159ms
memory: 46964kb
Test #20:
score: 5
Accepted
time: 152ms
memory: 53216kb
Extra Test:
score: 0
Extra Test Passed