QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492765#9155. 集合tuxuanming2024100 ✓184ms20060kbC++14987b2024-07-26 15:54:362024-07-26 15:54:37

Judging History

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

  • [2024-07-26 15:54:37]
  • 评测
  • 测评结果:100
  • 用时:184ms
  • 内存:20060kb
  • [2024-07-26 15:54:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef unsigned long long ull;
int n,m,q,a[N][3],b[N][3],res[N];
mt19937_64 rnd(31415926);
ull rd[N],va[N*3],vb[N*3],sa,sb;
void add(int i,ull t)
{
	for(int k=0;k<3;k++)
	{
		sa-=va[a[i][k]]*va[a[i][k]]*va[a[i][k]];
		va[a[i][k]]+=t*rd[i]*rd[i]*rd[i];
		sa+=va[a[i][k]]*va[a[i][k]]*va[a[i][k]];
		
		sb-=vb[b[i][k]]*vb[b[i][k]]*vb[b[i][k]];
		vb[b[i][k]]+=t*rd[i]*rd[i]*rd[i];
		sb+=vb[b[i][k]]*vb[b[i][k]]*vb[b[i][k]];
	}
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++) cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++) cin>>b[i][j];
	for(int i=1;i<=n;i++) rd[i]=rnd();
	for(int i=1,j=0;i<=n;i++)
	{
		while(j<n)
		{
			add(j+1,1);
			if(sa==sb) j++;
			else {add(j+1,-1); break;}
		}
		res[i]=j,add(i,-1);
	}
	while(q--)
	{
		int l,r; cin>>l>>r;
		cout<<(res[l]>=r?"Yes\n":"No\n");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 19ms
memory: 9840kb

Pretest #10:

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

Pretest #11:

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

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 100ms
memory: 9888kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 173ms
memory: 11788kb

Pretest #20:

score: 5
Accepted
time: 177ms
memory: 20040kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 103ms
memory: 9844kb

Test #16:

score: 5
Accepted
time: 96ms
memory: 9864kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 162ms
memory: 11620kb

Test #20:

score: 5
Accepted
time: 184ms
memory: 20060kb

Extra Test:

score: 0
Extra Test Passed