oj.uz

답안 #132691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132691 2019-07-19T10:51:39 Z keko37 Matching (CEOI11_mat) C++14
100 / 100
 1961 ms 46048 KB 
#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 1272 KB Output is correct
2 Correct 15 ms 1272 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1276 KB Output is correct
2 Correct 18 ms 1400 KB Output is correct
3 Correct 4 ms 504 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 7312 KB Output is correct
2 Correct 205 ms 7200 KB Output is correct
3 Correct 259 ms 7916 KB Output is correct
4 Correct 263 ms 7912 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 8188 KB Output is correct
2 Correct 299 ms 7484 KB Output is correct
3 Correct 212 ms 7668 KB Output is correct
4 Correct 206 ms 9380 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 8168 KB Output is correct
2 Correct 187 ms 7784 KB Output is correct
3 Correct 253 ms 7612 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1164 ms 35796 KB Output is correct
2 Correct 434 ms 36188 KB Output is correct
3 Correct 1308 ms 27356 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1059 ms 34704 KB Output is correct
2 Correct 1961 ms 32220 KB Output is correct
3 Correct 523 ms 46048 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1316 ms 33964 KB Output is correct
2 Correct 1112 ms 43232 KB Output is correct
3 Correct 1540 ms 32476 KB Output is correct
4 Correct 227 ms 36200 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1231 ms 34976 KB Output is correct
2 Correct 1605 ms 33144 KB Output is correct
3 Correct 514 ms 17512 KB Output is correct
4 Correct 439 ms 37084 KB Output is correct