Submission #132691

#	Time	Username	Problem	Language	Result	Execution time	Memory
132691		keko37	Matching (CEOI11_mat)	C++14	100 / 100	1961 ms	46048 KiB

mat

#include <bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 1050005;
const int MOD = 1000000007;
const int B = 31337;

int n, m, ofs;
int p[MAXN], h[MAXN];
vector <int> saz, sol;
int val[MAXN * 2], pot[MAXN], sum[MAXN], roll;
int br[MAXN * 2], prop[MAXN * 2];

inline int mul (int x, int y) {
	return x * 1ll * y % MOD;
}

inline int add (int x, int y) {
	x += y;
	if (x >= MOD) return x - MOD; return x;
}

inline int sub (int x, int y) {
	x -= y;
	if (x < 0) return x + MOD; return x;
}

void sazimanje () {
	for (int i=0; i<m; i++) {
		saz.push_back(h[i]);
	}
	sort(saz.begin(), saz.end());
	for (int i=0; i<m; i++) {
		h[i] = lower_bound(saz.begin(), saz.end(), h[i]) - saz.begin();
	}
}

void propagate (int x) {
	if (prop[x] == 0) return;
	if (x < ofs) {
		prop[2*x] += prop[x];
		prop[2*x+1] += prop[x];
	}
	val[x] = sub(val[x], mul(sum[br[x]], prop[x]));
	prop[x] = 0;
}

int gpos, gk;

void update (int x, int low, int high) {
	propagate(x);
	if (gpos < low || high < gpos) return;
	if (low == high) {
		val[x] = gk; br[x] = (gk > 0);
		return;
	}
	update(2*x, low, (low + high)/2);
	update(2*x+1, (low + high)/2+1, high);
	val[x] = add(mul(pot[br[2*x+1]], val[2*x]), val[2*x+1]);
	br[x] = br[2*x] + br[2*x+1];
}

void smanji () {
	prop[1]++;
}

void build () {
	ofs = 1;
	while (ofs < m) ofs *= 2;
	for (int i=0; i<n; i++) {
		val[h[i] + ofs] = i+1;
		br[h[i] + ofs] = 1;
	}
	for (int i = ofs-1; i > 0; i--) {
		val[i] = add(mul(pot[br[2*i+1]], val[2*i]), val[2*i+1]);
		br[i] = br[2*i] + br[2*i+1];
	}
}

void precompute () {
	roll = p[0];
	pot[0] = 1;
	for (int i=1; i<n; i++) {
		pot[i] = mul(pot[i-1], B);
		sum[i] = add(sum[i-1], pot[i-1]);
		roll = add(mul(roll, B), p[i]);
	}
}

void ispis () {
	for (int i=1; i<2*ofs; i++) {
		cout << "t " << i << " " << val[i] << " " << br[i] << "  " << prop[i] << endl;
	}
}

void rjesi () {
	if (val[1] == roll) sol.push_back(1);
	for (int i=1; i+n-1 < m; i++) {
		gpos = h[i-1]; gk = 0; update(1, 0, ofs-1);
		smanji();
		gpos = h[i+n-1]; gk = n; update(1, 0, ofs-1);
		if (val[1] == roll) sol.push_back(i+1);
	}
}

 
inline bool is( char c ) { return c >= '0' && c <= '9'; }
 
inline int read_int( ) {
    int num;
    char c;
    while( !is( c = getchar_unlocked( ) ) );
    num = c - '0';
    while( is( c = getchar_unlocked( ) ) ) num = num * 10 + c - '0';
    return num;
}

#define pc(x) putchar_unlocked(x);
inline void writeInt (int n) {
    int N = n, rev, count = 0;
    rev = N;
    if (N == 0) { pc('0'); pc('\n'); return ;}
    while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s
    rev = 0;
    while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}  //store reverse of N in rev
    while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
	while (count--) pc('0');
}

int main () {
	n = read_int(); m = read_int();
	for (int i=0; i<n; i++) {
		p[i] = read_int();
	}
	for (int i=0; i<m; i++) {
		h[i] = read_int();
	}
	sazimanje();
	precompute();
	build();
	rjesi();
	writeInt(sol.size()); putchar('\n');
	for (int i=0; i<sol.size(); i++) {
		writeInt(sol[i]);
		putchar(' ');
	}
	return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int add(int, int)':
mat.cpp:23:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (x >= MOD) return x - MOD; return x;
  ^~
mat.cpp:23:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (x >= MOD) return x - MOD; return x;
                                ^~~~~~
mat.cpp: In function 'int sub(int, int)':
mat.cpp:28:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (x < 0) return x + MOD; return x;
  ^~
mat.cpp:28:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (x < 0) return x + MOD; return x;
                             ^~~~~~
mat.cpp: In function 'int main()':
mat.cpp:146:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<sol.size(); 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