QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489555 | #9155. 集合 | xinhaowen | 100 ✓ | 477ms | 84520kb | C++14 | 1.8kb | 2024-07-24 21:21:33 | 2024-07-24 21:21:33 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<unordered_map>
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
template<typename T>void read(T &x){
x=0;bool f=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f)x=-x;
}
void write(char x){putchar(x);}
template<typename T>void write(T x){
if(x<0)putchar('-'),x=-x;
char stk[104];int cnt=0;
do stk[++cnt]=x%10+48,x/=10;while(x);
for(;cnt;)putchar(stk[cnt--]);
}
template<typename T,typename ...Args>void read(T &x,Args &...args){read(x);read(args...);}
template<typename T,typename ...Args>void write(T x,Args ...args){write(x);write(args...);}
template<typename T>T min(T x,T y){return x<y?x:y;}
template<typename T>T max(T x,T y){return x>y?x:y;}
const int maxn=6e5+4,P=19491001;int n,m,q,ans[maxn],tot;std::unordered_map<unsigned long long,int>mp;
unsigned long long hash[2][maxn],pw[12*maxn],H[2];
struct _{int x,y,z;}a[maxn],b[maxn];
void change(int x,int loc,bool op,int val){
unsigned long long &tmp=hash[op][x];
if(tmp&&mp.find(tmp)!=mp.end())H[op]-=pw[mp[tmp]];
unsigned long long shi=pw[loc]*val;
tmp+=shi;
if(tmp&&mp.find(tmp)==mp.end())mp[tmp]=++tot;
if(tmp)H[op]+=pw[mp[tmp]];
}
void work(int i,int op){
change(a[i].x,i,0,op),change(b[i].x,i,1,op),
change(a[i].y,i,0,op),change(b[i].y,i,1,op),
change(a[i].z,i,0,op),change(b[i].z,i,1,op);
}
signed main(){
read(n,m,q);pw[0]=1;
for(int i=1;i<=12*n;++i)pw[i]=pw[i-1]*P;
for(int i=1;i<=n;++i)read(a[i].x,a[i].y,a[i].z);
for(int i=1;i<=n;++i)read(b[i].x,b[i].y,b[i].z);
for(int l=1,r=0;l<=n;){
for(;r<l;)++r,work(r,1);
for(;r<=n&&H[0]==H[1];)r++,work(r,1);
work(r,-1);r--;ans[l]=r;work(l,-1);l++;
}
for(;q--;){
int x,y;read(x,y);
puts(ans[x]>=y?"Yes":"No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 9976kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 9748kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 9756kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 9764kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 9672kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 9756kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 9780kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 9660kb
Pretest #9:
score: 5
Accepted
time: 7ms
memory: 9712kb
Pretest #10:
score: 5
Accepted
time: 7ms
memory: 9772kb
Pretest #11:
score: 5
Accepted
time: 473ms
memory: 81836kb
Pretest #12:
score: 5
Accepted
time: 430ms
memory: 78380kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 10044kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 10408kb
Pretest #15:
score: 5
Accepted
time: 39ms
memory: 10076kb
Pretest #16:
score: 5
Accepted
time: 42ms
memory: 10188kb
Pretest #17:
score: 5
Accepted
time: 17ms
memory: 16500kb
Pretest #18:
score: 5
Accepted
time: 25ms
memory: 17104kb
Pretest #19:
score: 5
Accepted
time: 477ms
memory: 77904kb
Pretest #20:
score: 5
Accepted
time: 402ms
memory: 80664kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9760kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 9628kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9736kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9740kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9632kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 9756kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 10008kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9768kb
Test #9:
score: 5
Accepted
time: 11ms
memory: 9796kb
Test #10:
score: 5
Accepted
time: 11ms
memory: 9708kb
Test #11:
score: 5
Accepted
time: 445ms
memory: 84520kb
Test #12:
score: 5
Accepted
time: 400ms
memory: 78116kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 10132kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 10208kb
Test #15:
score: 5
Accepted
time: 50ms
memory: 12432kb
Test #16:
score: 5
Accepted
time: 50ms
memory: 10228kb
Test #17:
score: 5
Accepted
time: 22ms
memory: 18312kb
Test #18:
score: 5
Accepted
time: 25ms
memory: 15272kb
Test #19:
score: 5
Accepted
time: 417ms
memory: 78836kb
Test #20:
score: 5
Accepted
time: 454ms
memory: 82048kb
Extra Test:
score: 0
Extra Test Passed