QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511397#9155. 集合songke100 ✓1135ms85736kbC++141.2kb2024-08-09 20:28:342024-08-09 20:28:34

Judging History

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

  • [2024-08-09 20:28:34]
  • 评测
  • 测评结果:100
  • 用时:1135ms
  • 内存:85736kb
  • [2024-08-09 20:28:34]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define G(i,l,r) for(int i=(l),i##end=(r);i>=i##end;--i)
#define x first
#define y second
#define int long long
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define ep emplace_back
using namespace std;
int base=1233,m,q,qp[600009],has[12000009],mod=1e18+3;
unordered_map<ll,int> ma;mt19937_64 rnd(time(0));
int f[200009];int err;
vector<int> a[200009],b[200009];
void add(int i)
{
  	for(auto u:a[i])
	{
	  	err-=ma[has[u]]==1;
		err+=ma[has[u]]==0;
		ma[has[u]]--;
		has[u]^=qp[i];
		err+=ma[has[u]]==0;
		err-=ma[has[u]]==-1;
		ma[has[u]]++;
	}
	for(auto u:b[i])
	{
	  	err-=ma[has[u+m]]==-1;
		err+=ma[has[u+m]]==0;
		ma[has[u+m]]++;
		has[u+m]^=qp[i];
		err+=ma[has[u+m]]==0;
		err-=ma[has[u+m]]==1;
		ma[has[u+m]]--;
	}
}
main()
{
  	int n;
	cin>>n>>m>>q;
	qp[0]=1;
	F(i,1,n) qp[i]=rnd();
	F(i,1,n)F(j,0,2){int x;cin>>x;a[i].ep(x);}
	F(i,1,n)F(j,0,2){int x;cin>>x;b[i].ep(x);}
	F(i,1,n)
	{
	  	f[i]=f[i-1];
		add(i);
		while(err && f[i]<i) add(++f[i]);
	}
	F(i,1,q)
	{
		int l,r;
		cin>>l>>r;
		if(l>f[r]) cout<<"Yes\n";
		else cout<<"No\n";
	}
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 91ms
memory: 18344kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 497ms
memory: 83920kb

Pretest #12:

score: 5
Accepted
time: 522ms
memory: 81288kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 464ms
memory: 18524kb

Pretest #16:

score: 5
Accepted
time: 520ms
memory: 18912kb

Pretest #17:

score: 5
Accepted
time: 41ms
memory: 23628kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 1032ms
memory: 81000kb

Pretest #20:

score: 5
Accepted
time: 1131ms
memory: 85524kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 92ms
memory: 18312kb

Test #10:

score: 5
Accepted
time: 92ms
memory: 18644kb

Test #11:

score: 5
Accepted
time: 447ms
memory: 79404kb

Test #12:

score: 5
Accepted
time: 465ms
memory: 78420kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 494ms
memory: 17812kb

Test #16:

score: 5
Accepted
time: 492ms
memory: 18132kb

Test #17:

score: 5
Accepted
time: 30ms
memory: 23692kb

Test #18:

score: 5
Accepted
time: 37ms
memory: 23824kb

Test #19:

score: 5
Accepted
time: 947ms
memory: 78760kb

Test #20:

score: 5
Accepted
time: 1135ms
memory: 85736kb

Extra Test:

score: 0
Extra Test Passed