oj.uz

Submission #218219

# Submission time Handle Problem Language Result Execution time Memory
218219 2020-04-01T14:31:20 Z Andrei_Cotor Matching (CEOI11_mat) C++11
100 / 100
 435 ms 48076 KB 
//alternativ cu aib determin pozitia relativa a fiecarui element cand compar.
//setu asta-i scammer rau... 105mb 1e6 perechi de valori...
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N[1000005],H[1000005];
int P[1000005];
int Smaller[1000005],Greater[1000005];
int St[1000005],Dr[1000005];
int Poz[1000005];
vector<int> Rez;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n,m;
	cin>>n>>m;

	for(int i=1; i<=n; i++)
	{
		int x;
		cin>>x;
		N[x]=i;
		Poz[i]=x;
	}

	for(int i=1; i<=n; i++)
	{
		St[i]=i-1;
		Dr[i]=i+1;
	}

	for(int i=n; i>=1; i--)
	{
		int ind=N[i];
		Greater[i]=Poz[Dr[ind]];
		Smaller[i]=Poz[St[ind]];

		//sterg ind
		St[Dr[ind]]=St[ind];
		Dr[St[ind]]=Dr[ind];
	}

	for(int i=1; i<=m; i++)
		cin>>H[i];

	for(int i=2; i<=n; i++)
	{
		int k=P[i-1];
		while(k!=0)
		{
			if(Smaller[k+1]!=0 && N[i-k-1+Smaller[k+1]]>N[i])
			{
				k=P[k];
				continue;
			}

			if(Greater[k+1]!=0 && N[i-k-1+Greater[k+1]]<N[i])
			{
				k=P[k];
				continue;
			}

			break;
		}

		P[i]=k+1;
	}

	int l=1;
	for(int i=2; i<=m; i++)
	{
		while(l!=0)
		{
			if(Smaller[l+1]!=0 && H[i-l-1+Smaller[l+1]]>H[i])
			{
				l=P[l];
				continue;
			}

			if(Greater[l+1]!=0 && H[i-l-1+Greater[l+1]]<H[i])
			{
				l=P[l];
				continue;
			}

			break;
		}

		l++;

		if(l==n)
		{
			Rez.push_back(i-n+1);
			l=P[l];
		}
	}

	cout<<Rez.size()<<"\n";
	for(auto el:Rez)
		cout<<el<<" ";
	cout<<"\n";
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 768 KB Output is correct
2 Correct 8 ms 816 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 768 KB Output is correct
2 Correct 8 ms 768 KB Output is correct
3 Correct 6 ms 384 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3704 KB Output is correct
2 Correct 29 ms 2560 KB Output is correct
3 Correct 47 ms 4728 KB Output is correct
4 Correct 44 ms 4728 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4600 KB Output is correct
2 Correct 35 ms 3192 KB Output is correct
3 Correct 39 ms 4088 KB Output is correct
4 Correct 52 ms 4696 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4216 KB Output is correct
2 Correct 60 ms 3936 KB Output is correct
3 Correct 36 ms 3832 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 20984 KB Output is correct
2 Correct 435 ms 48076 KB Output is correct
3 Correct 126 ms 11896 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 20984 KB Output is correct
2 Correct 150 ms 11060 KB Output is correct
3 Correct 403 ms 43492 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14580 KB Output is correct
2 Correct 243 ms 21976 KB Output is correct
3 Correct 160 ms 14840 KB Output is correct
4 Correct 294 ms 46092 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 16376 KB Output is correct
2 Correct 165 ms 14968 KB Output is correct
3 Correct 80 ms 9336 KB Output is correct
4 Correct 296 ms 43872 KB Output is correct