QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489555#9155. 集合xinhaowen100 ✓477ms84520kbC++141.8kb2024-07-24 21:21:332024-07-24 21:21:33

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 21:21:33]
  • 评测
  • 测评结果:100
  • 用时:477ms
  • 内存:84520kb
  • [2024-07-24 21:21:33]
  • 提交

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