Submission #364461

#	Time	Username	Problem	Language	Result	Execution time	Memory
364461		arnold518	Matching (CEOI11_mat)	C++14	100 / 100	1071 ms	44184 KiB

mat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, M;
int A[MAXN+10], B[MAXN+10], C[MAXN+10];
int fail[MAXN+10];

struct BIT
{
	int tree[MAXN+10];
	void update(int i, int k) { for(; i<=N; i+=(i&-i)) tree[i]+=k; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit1, bit2;

vector<int> comp;

int main()
{
	scanf("%d%d", &M, &N);
	for(int i=1; i<=M; i++) scanf("%d", &C[i]);
	for(int i=1; i<=M; i++) B[C[i]]=i;
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);

	comp=vector<int>(A+1, A+N+1);
	sort(comp.begin(), comp.end());
	for(int i=1; i<=N; i++) A[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;
		
	for(int i=2, j=1; i<=M;)
	{
		if(j<=M && bit2.query(B[j])==bit1.query(B[i]))
		{
			fail[i]=j;
			bit1.update(B[i], 1);
			bit2.update(B[j], 1);
			i++; j++;
		}
		else
		{
			if(j!=1)
			{
				for(int k=j-1; k>fail[j-1]; k--)
				{
					bit2.update(B[k], -1);
					bit1.update(B[i-k], -1);
				}
				j=fail[j-1]+1;
			}
			else i++;
		}	
	}

	memset(bit1.tree, 0, sizeof(bit1.tree));
	memset(bit2.tree, 0, sizeof(bit2.tree));
	vector<int> ans;
	for(int i=1, j=1; i<=N;)
	{
		if(j<=M && bit2.query(B[j])==bit1.query(A[i]))
		{
			bit1.update(A[i], 1);
			bit2.update(B[j], 1);
			i++; j++;
			if(j==M+1)
			{
				ans.push_back(i-M);
			}
		}
		else
		{
			if(j!=1)
			{
				for(int k=j-1; k>fail[j-1]; k--)
				{
					bit2.update(B[k], -1);
					bit1.update(A[i-k], -1);
				}
				j=fail[j-1]+1;
			}
			else i++;
		}
	}
	printf("%d\n", ans.size());
	for(auto it : ans) printf("%d ", it);
	printf("\n");
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:87:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   87 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
mat.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d%d", &M, &N);
      |  ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  for(int i=1; i<=M; i++) scanf("%d", &C[i]);
      |                          ~~~~~^~~~~~~~~~~~~
mat.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~

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