QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497672#9155. 集合Clonoth100 ✓66ms28292kbC++171.8kb2024-07-29 15:44:452024-07-29 15:44:46

Judging History

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

  • [2024-07-29 15:44:46]
  • 评测
  • 测评结果:100
  • 用时:66ms
  • 内存:28292kb
  • [2024-07-29 15:44:45]
  • 提交

answer

#include<bits/stdc++.h>
#define fir first
#define sec second
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
template<typename type>
inline void chmin(type &x,const type &y)
{
	if(y<x)
		x=y;
}
template<typename type>
inline void chmax(type &x,const type &y)
{
	if(x<y)
		x=y;
}
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x)
{
	x=0;
	bool f=false;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')
		x=x*10+(ch^48),ch=getchar();
	if(f)
		x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y)
{
	read(x),read(y...);
}
constexpr int Max=2e5+10,Size=Max*3;
mt19937_64 rng(666);
ull num[Max];
int n,m,q;
int a[Max][3],b[Max][3],val[Max];
struct shengqile
{
	ull f[Size],ans;
	inline void add(int x,int y)// a[x] = y
	{
		ans-=f[y]*f[y];
		f[y]^=num[x];
		ans+=f[y]*f[y];
	}
}A,B;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	read(n,m,q);
	for(int i=1;i<=n;++i)
		num[i]=rng();
	for(int i=1;i<=n;++i)
		read(a[i][0],a[i][1],a[i][2]);
	for(int i=1;i<=n;++i)
		read(b[i][0],b[i][1],b[i][2]);
	for(int i=1,j=0;i<=n;++i)
	{
		val[i]=val[i-1];
		while(A.ans==B.ans)
		{
			val[i]=j;
			if(j==n)
				break;
			++j;
			for(int x:a[j])
				A.add(j,x);
			for(int x:b[j])
				B.add(j,x);
		}
		for(int x:a[i])
			A.add(i,x);
		for(int x:b[i])
			B.add(i,x);
	}
	int l,r;
	while(q--)
	{
		read(l,r);
		if(val[l]>=r)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 9768kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 11820kb

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 11792kb

Pretest #4:

score: 5
Accepted
time: 2ms
memory: 11816kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 9856kb

Pretest #6:

score: 5
Accepted
time: 0ms
memory: 11888kb

Pretest #7:

score: 5
Accepted
time: 0ms
memory: 11816kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 11756kb

Pretest #9:

score: 5
Accepted
time: 8ms
memory: 11824kb

Pretest #10:

score: 5
Accepted
time: 9ms
memory: 13804kb

Pretest #11:

score: 5
Accepted
time: 15ms
memory: 17968kb

Pretest #12:

score: 5
Accepted
time: 18ms
memory: 17996kb

Pretest #13:

score: 5
Accepted
time: 0ms
memory: 11776kb

Pretest #14:

score: 5
Accepted
time: 2ms
memory: 11992kb

Pretest #15:

score: 5
Accepted
time: 34ms
memory: 17768kb

Pretest #16:

score: 5
Accepted
time: 39ms
memory: 18972kb

Pretest #17:

score: 5
Accepted
time: 3ms
memory: 13808kb

Pretest #18:

score: 5
Accepted
time: 0ms
memory: 14800kb

Pretest #19:

score: 5
Accepted
time: 53ms
memory: 18888kb

Pretest #20:

score: 5
Accepted
time: 66ms
memory: 28276kb

Final Tests

Test #1:

score: 5
Accepted
time: 0ms
memory: 11844kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 11912kb

Test #3:

score: 5
Accepted
time: 0ms
memory: 11784kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 11808kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 9728kb

Test #6:

score: 5
Accepted
time: 2ms
memory: 11900kb

Test #7:

score: 5
Accepted
time: 0ms
memory: 11900kb

Test #8:

score: 5
Accepted
time: 0ms
memory: 11908kb

Test #9:

score: 5
Accepted
time: 4ms
memory: 13944kb

Test #10:

score: 5
Accepted
time: 3ms
memory: 11884kb

Test #11:

score: 5
Accepted
time: 16ms
memory: 17996kb

Test #12:

score: 5
Accepted
time: 15ms
memory: 15876kb

Test #13:

score: 5
Accepted
time: 2ms
memory: 11820kb

Test #14:

score: 5
Accepted
time: 0ms
memory: 9904kb

Test #15:

score: 5
Accepted
time: 38ms
memory: 18552kb

Test #16:

score: 5
Accepted
time: 34ms
memory: 18428kb

Test #17:

score: 5
Accepted
time: 0ms
memory: 13880kb

Test #18:

score: 5
Accepted
time: 0ms
memory: 12828kb

Test #19:

score: 5
Accepted
time: 48ms
memory: 20000kb

Test #20:

score: 5
Accepted
time: 63ms
memory: 28292kb

Extra Test:

score: 0
Extra Test Passed