Submission #132631

#	Time	Username	Problem	Language	Result	Execution time	Memory
132631		patrikpavic2	Matching (CEOI11_mat)	C++17	100 / 100	1096 ms	40376 KiB

mat

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e6 + 500;
const int BS = 1001347;
const int MOD = 1e9 + 7;


inline int add(const int &A, const int &B){
	if(A + B >= MOD) return A + B - MOD;
	return A + B;
}

inline int sub(const int &A, const int &B){
	if(A - B < 0) return A - B + MOD;
	return A - B;
}

inline int mul(const int &A, const int &B){
	return (ll)A * B % MOD;
}

int loga[N][2], pot[N], n, m, A[N], P[N];
vector < int > saz;

void add(int i,int k, int x){
	int fl = 0;
	if(x < 0) x *= -1, fl = 1;
	for(; i < N; i += i & -i){
		if(fl) loga[i][k] = sub(loga[i][k], x);
		else   loga[i][k] = add(loga[i][k], x);
	}
}

int query(int i,int k){
	int ret = 0;
	for(; i ; i -= i & -i)
		ret = add(ret, loga[i][k]);
	return ret;
}

int main(){
	scanf("%d%d", &m, &n);
	for(int i = 1;i <= m;i++){
		int x; scanf("%d", &x); 
		P[x - 1] = i;
	}
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
		saz.PB(A[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for(int i = 0;i < n;i++){
		A[i] = lower_bound(saz.begin(), saz.end(), A[i]) - saz.begin() + 1;
	}	
	pot[0] = 1;
	for(int i = 1;i < n;i++){
		pot[i] = mul(pot[i - 1], BS);
	}
	int traz = 0;
	for(int i = 0;i < m;i++){
		traz = add(traz, mul(pot[i], i - query(P[i], 0)));
		add(P[i], 0, 1);
	}
	memset(loga, 0, sizeof(loga));
	int cur = 0;
	vector < int > sol;
	for(int i = 0;i < n;i++){
		if(i >= m){
			add(A[i - m], 0, -1);
			add(A[i - m], 1, -pot[i - m]);
			cur = sub(cur, query(A[i - m], 1));
		}
		cur = add(cur, mul(pot[i], min(i, m - 1) - query(A[i], 0)));
		add(A[i], 0, 1); 
		add(A[i], 1, pot[i]);
		if(i >= m - 1){
			if(mul(traz, pot[i - m + 1]) == cur)
				sol.PB(i - m + 2);
		}
	}
	printf("%d\n", (int)sol.size());
	for(int x : sol)
		printf("%d ", x);
	printf("\n");
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:55:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x); 
          ~~~~~^~~~~~~~~~
mat.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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