| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 132690 |
2019-07-19T10:46:16 Z |
keko37 |
Matching (CEOI11_mat) |
C++14 |
|
2000 ms |
43360 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;
}
void update (int x, int pos, int low, int high, int k) {
propagate(x);
if (pos < low || high < pos) return;
if (low == high) {
val[x] = k; br[x] = (k > 0);
return;
}
update(2*x, pos, low, (low + high)/2, k);
update(2*x+1, pos, (low + high)/2+1, high, k);
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++) {
update(1, h[i-1], 0, ofs-1, 0);
smanji();
update(1, h[i+n-1], 0, ofs-1, n);
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:144:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<sol.size(); i++) {
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1476 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1400 KB |
Output is correct |
| 2 |
Correct |
19 ms |
1400 KB |
Output is correct |
| 3 |
Correct |
5 ms |
508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
218 ms |
7280 KB |
Output is correct |
| 3 |
Correct |
264 ms |
8144 KB |
Output is correct |
| 4 |
Correct |
269 ms |
8048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
203 ms |
8328 KB |
Output is correct |
| 2 |
Correct |
351 ms |
7488 KB |
Output is correct |
| 3 |
Correct |
220 ms |
7788 KB |
Output is correct |
| 4 |
Correct |
212 ms |
9444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
8480 KB |
Output is correct |
| 2 |
Correct |
199 ms |
7912 KB |
Output is correct |
| 3 |
Correct |
240 ms |
7804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1251 ms |
35776 KB |
Output is correct |
| 2 |
Correct |
432 ms |
36188 KB |
Output is correct |
| 3 |
Correct |
1504 ms |
27484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1160 ms |
34836 KB |
Output is correct |
| 2 |
Execution timed out |
2061 ms |
32348 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1417 ms |
34136 KB |
Output is correct |
| 2 |
Correct |
1163 ms |
43360 KB |
Output is correct |
| 3 |
Correct |
1627 ms |
32776 KB |
Output is correct |
| 4 |
Correct |
224 ms |
36320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1368 ms |
34992 KB |
Output is correct |
| 2 |
Correct |
1686 ms |
33324 KB |
Output is correct |
| 3 |
Correct |
548 ms |
17892 KB |
Output is correct |
| 4 |
Correct |
422 ms |
37112 KB |
Output is correct |
