# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
698292 |
2023-02-13T04:28:50 Z |
DennisTran |
Matching (CEOI11_mat) |
C++17 |
|
1442 ms |
61068 KB |
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
inline void add(int &x, int val) {
x += val;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
}
int N, M, ori, a[MAXN], h[MAXN], it[4 * MAXN], Pow[MAXN], Pow1[MAXN], lazy[4 * MAXN], sl[4 * MAXN];
vector <int> nen;
void down(int id) {
FOR(i, id * 2, id * 2 + 1) {
lazy[i] += lazy[id];
add(it[i], 1ll * Pow1[sl[i]] * lazy[id] % MOD);
} lazy[id] = 0;
}
void update(int id, int l, int r, int x, int val) {
if (l == r) {
if (val > 0) it[id] = val, sl[id]++;
else it[id] = 0, sl[id]--;
return;
}
down(id);
int mid = l + r >> 1;
if (mid >= x) update(id * 2, l, mid, x, val);
else update(id * 2 + 1, mid + 1, r, x, val);
it[id] = 1ll * Pow[sl[id * 2 + 1]] * it[id * 2] % MOD;
add(it[id], it[id * 2 + 1]);
sl[id] = sl[id * 2] + sl[id * 2 + 1];
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
file("TASK");
cin >> N >> M;
Pow[0] = 1;
Pow1[0] = 0;
FOR(i, 1, N) {
cin >> a[i];
ori = (1ll * M * ori + a[i]) % MOD;
Pow[i] = 1ll * Pow[i - 1] * M % MOD;
Pow1[i] = (1ll * Pow1[i - 1] * M + 1) % MOD;
}
FOR(i, 1, M) cin >> h[i], nen.emplace_back(h[i]);
sort(ALL(nen));
FOR(i, 1, M) h[i] = lower_bound(ALL(nen), h[i]) - nen.begin() + 1;
FOR(i, 1, N) update(1, 1, M, h[i], i);
vector <int> ans;
if (it[1] == ori) ans.emplace_back(1);
FOR(i, N + 1, M) {
update(1, 1, M, h[i - N], -1);
add(it[1], -Pow1[sl[1]]);
lazy[1]--;
update(1, 1, M, h[i], N);
if (it[1] == ori) ans.emplace_back(i - N + 1);
}
cout << ans.size() << '\n';
for (int x : ans) cout << x << ' ';
cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
Compilation message
mat.cpp: In function 'void update(int, int, int, int, int)':
mat.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid = l + r >> 1;
| ~~^~~
mat.cpp: In function 'int main()':
mat.cpp:9:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:49:5: note: in expansion of macro 'file'
49 | file("TASK");
| ^~~~
mat.cpp:9:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:49:5: note: in expansion of macro 'file'
49 | file("TASK");
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
1480 KB |
Output is correct |
2 |
Correct |
16 ms |
1460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
1496 KB |
Output is correct |
2 |
Correct |
16 ms |
1428 KB |
Output is correct |
3 |
Correct |
3 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
8472 KB |
Output is correct |
2 |
Correct |
190 ms |
9564 KB |
Output is correct |
3 |
Correct |
243 ms |
11024 KB |
Output is correct |
4 |
Correct |
243 ms |
10956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
197 ms |
9028 KB |
Output is correct |
2 |
Correct |
250 ms |
10436 KB |
Output is correct |
3 |
Correct |
210 ms |
10736 KB |
Output is correct |
4 |
Correct |
196 ms |
11524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
188 ms |
9168 KB |
Output is correct |
2 |
Correct |
181 ms |
10312 KB |
Output is correct |
3 |
Correct |
214 ms |
10324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1126 ms |
45092 KB |
Output is correct |
2 |
Correct |
1155 ms |
61068 KB |
Output is correct |
3 |
Correct |
1146 ms |
39164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1034 ms |
45232 KB |
Output is correct |
2 |
Correct |
1442 ms |
39736 KB |
Output is correct |
3 |
Correct |
1235 ms |
57256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1186 ms |
40696 KB |
Output is correct |
2 |
Correct |
946 ms |
50480 KB |
Output is correct |
3 |
Correct |
1379 ms |
43576 KB |
Output is correct |
4 |
Correct |
728 ms |
59184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1194 ms |
41452 KB |
Output is correct |
2 |
Correct |
1265 ms |
43852 KB |
Output is correct |
3 |
Correct |
519 ms |
22192 KB |
Output is correct |
4 |
Correct |
887 ms |
58404 KB |
Output is correct |