QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#660691	#9356. LRU Algorithm	XG0000^#	TL	0ms	4076kb	C++14	1.2kb	2024-10-20 12:45:37	2024-10-20 12:45:37

Judging History

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

[2024-10-20 12:45:37]
评测

测评结果：TL
用时：0ms
内存：4076kb

查看

[2024-10-20 12:45:37]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=5010,P=13331;
vector<ull> H[N],H1[N];
vector<int> s;
int T,n,q,a[N];

bool find_site(vector<ull> &s,ull h)
{
	auto t=lower_bound(s.begin(),s.end(),h);
	if(t!=s.end() && (*t)==h) return 1;
	return 0;
}

int main(void)
{
	scanf("%d",&T);
	while(T--)
	{
		for(int i=1;i<=n;i++) H[i].clear(),H1[i].clear();
		scanf("%d%d",&n,&q);
		for(int i=1,x;i<=n;i++) 
		{
			scanf("%d",&x);
			auto t=s.begin();
			while(t!=s.end())
			{
				if((*t)==x) {s.erase(t);break;}
				t++;
			}
			s.push_back(x);
			ull hh=0;
			for(int j=s.size()-1;j>=0;j--) hh=hh*P+s[j],H[s.size()-j].push_back(hh);
			H1[s.size()].push_back(hh);
		}
		for(int i=1;i<=n;i++) sort(H[i].begin(),H[i].end()),sort(H1[i].begin(),H1[i].end());
		while(q--)
		{
			int m,len;
			bool flag=0;
			ull hh=0;
			scanf("%d",&m);len=m;
			while(m--)
			{
				int x;
				scanf("%d",&x);
				if(!x) {len--;flag=1;continue;}
				hh=hh*P+x;
			}
			if(flag)
			{
				if(find_site(H1[len],hh)) puts("Yes");
				else puts("No");
			}
			else
			{
				if(find_site(H[len],hh)) puts("Yes");
				else puts("No");
			}
		}
	}

	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 4076kb

input:

1
7 5
4 3 4 2 3 1 4
1 4
2 2 3
3 3 2 1
4 4 1 3 2
4 3 4 0 0

output:

Yes
No
No
Yes
Yes

result:

ok 5 lines

Test #2:

score: -100

Time Limit Exceeded

input:

105
50 10
23 30 34 20 27 11 21 29 12 7 21 42 45 48 8 15 6 16 19 35 16 14 29 11 31 18 22 4 45 22 14 4 13 40 43 48 27 15 15 15 15 10 15 11 31 37 34 34 50 14
1 25
2 23 6
3 29 21 11
4 12 29 18 39
5 29 21 11 27 20
6 21 10 9 3 34 14
7 49 36 36 43 50 50 35
8 12 29 21 11 27 20 34 30
9 11 27 20 34 30 23 0 0 ...

output:

No
No
Yes
No
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
Yes
No
No
No
Yes
No
Yes
Yes
No
No
Yes
No
No
No
No
No
Yes
No
Yes
No
Yes
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
Yes
...