Submission #891297

#	Time	Username	Problem	Language	Result	Execution time	Memory
891297		bibocat	Matching (CEOI11_mat)	C++14	0 / 100	100 ms	37824 KiB

mat

#include<iostream>
#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<deque>
#include<math.h>
#include<ctime>

using namespace std;

#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define long long long
#define mp(a,b) make_pair(a,b)
#define FI first
#define SE second


#define N 1000001

const long mod = 998244353;
    
long fminn[N],fmaxx[N];

long a[N];
long b[N];
long kmp[N];
long n,m;
bool sosanh(long i,long j,long a[],long b[])
{
	if(i == 0)
		return 1;
	if(i == 1)
		return (a[i]-a[i-1])*(b[j]-b[j-1]) > 0;
	long tmp1 = j - i + fminn[i];
	if(fminn[i] == m+1)
		tmp1 = m+1;
	long tmp2 = j - i + fmaxx[i];
	if(fmaxx[i] == m+2)
		tmp2 = m+2;
	//cout << tmp1 << " " << tmp2 <<" "<<b[j] << endl;
	if(b[j] < b[tmp1] && b[j] > b[tmp2]) return true;
	return false;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    
    cin >> n >> m;


    queue<long> d;


    for(long i = 0;i < n;i++)
    	cin >> a[i];
    a[n+1] = n+1;;
    for(long i = 0;i < m;i++)
    	cin >> b[i];
    a[m+1] = 2e9;
    a[0] = 0;
    b[0] = 0;
    b[m+1] = 2e9;
    b[m+2] = 2e9;
    a[m+2] = 2e9;
    for(long i = 0;i < n;i++)
    {
    	while(d.empty() == false)
    	{
    		if(a[d.front()] < a[i])
    			d.pop();
    		else
    			break;
    	}
    	if(d.empty() == true)
    		fminn[i] = m+1;
    	else
    		fminn[i] = d.front();
    	d.push(i);

    }

    while(d.empty() ==false)
    	d.pop();

    for(long i = 0;i < n;i++)
    {
    	while(d.empty() == false)
    	{
    		if(a[d.front()] > a[i])
    			d.pop();
    		else
    			break;
    	}
    	if(d.empty() == true)
    		fmaxx[i] = m+2;
    	else
    		fmaxx[i] = d.front();
    	d.push(i);
    }

    long j = 1;
    kmp[0] = 0;
    
    for(long i = 1;i < n;i++)
    {
    	j = kmp[i-1];
    	if(j > 0 && !sosanh(j,i,a,a))
    		j = kmp[j-1];
    	
    	if(sosanh(j,i,a,a))
    		j++;
    	kmp[i] = j;

    }

   // cout << sosanh(2,3,a,b) << endl;
    j = 0;
    std::vector<long> kq;
   for(long i = 0;i < m;i++)
    {
    	while(j > 0 && !sosanh(j,i,a,b))
    		j = kmp[j-1];
        if(sosanh(j,i,a,b))
            j++;
    	if(j == n-1)
    		kq.push_back(i-n+1);
    	//cout << j << endl;
    }

    cout << kq.size() << endl;
    for(long i = 0;i < kq.size();i++)
    	cout << kq[i] + 1 << " ";
    cerr<<"Times:  "<<TIME<<endl;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:141:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(long i = 0;i < kq.size();i++)
      |                    ~~^~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10