#include <bits/stdc++.h>
using namespace std;
template<class T> struct Seg { // comb(ID,b) = b
const T ID = 1e9; T comb(T a, T b) { return min(a,b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // min on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int M, Q; cin >> M >> Q;
vector<int> p(M);
Seg<int> st;
st.init(M + 1);
for (int i = 0; i < M; i++) {
cin >> p[i];
st.upd(i, 0);
}
sort(p.begin(), p.end());
int mx = 10000000;
int res[mx];
int lpf[mx];
for (int i = 0; i < mx; i++) {
lpf[i] = -1;
}
for (int j = 0; j < p.size(); j++) {
for (int i = p[j]; i < mx; i += p[j]) {
lpf[i] = j;
}
}
for (int i = 1; i < mx; i++) {
int ans = 1e9;
if (lpf[i] == -1) {
ans = st.query(0, M - 1) + 1;
} else {
vector<int> invalid;
invalid.push_back(-1);
int x = i;
while (lpf[x] != -1) {
invalid.push_back(lpf[x]);
int a = p[lpf[x]];
while (x % a == 0) x /= a;
}
sort(invalid.begin(), invalid.end());
invalid.push_back(p.size());
for (int j = 0; j < (int)invalid.size() - 1; j++) {
if (invalid[j] + 1 <= invalid[j + 1] - 1) {
ans = min(ans, st.query(invalid[j] + 1, invalid[j + 1] - 1) + 1);
}
}
for (int j: invalid) {
if (j >= 0 && j < (int)p.size()) {
st.upd(j, ans);
}
}
}
res[i] = ans;
}
while (Q--) {
int x;
cin >> x;
if (res[x] == (int)1e9) {
cout << "oo\n";
} else {
cout << res[x] << '\n';
}
}
}
Compilation message
brunhilda.cpp: In function 'int main()':
brunhilda.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int j = 0; j < p.size(); j++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
345 ms |
78488 KB |
Output isn't correct |
| 2 |
Execution timed out |
1102 ms |
78504 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1094 ms |
78540 KB |
Time limit exceeded |
| 4 |
Correct |
294 ms |
78572 KB |
Output is correct |
| 5 |
Correct |
512 ms |
78568 KB |
Output is correct |
| 6 |
Incorrect |
311 ms |
78580 KB |
Output isn't correct |
| 7 |
Execution timed out |
1094 ms |
78480 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1104 ms |
78568 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1089 ms |
78504 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1101 ms |
78540 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1100 ms |
78544 KB |
Time limit exceeded |
| 12 |
Correct |
270 ms |
78584 KB |
Output is correct |
| 13 |
Execution timed out |
1103 ms |
78480 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1099 ms |
78540 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1097 ms |
78548 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1102 ms |
78492 KB |
Time limit exceeded |
| 17 |
Correct |
639 ms |
78572 KB |
Output is correct |
| 18 |
Correct |
286 ms |
78576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
715 ms |
78800 KB |
Output is correct |
| 2 |
Correct |
888 ms |
79660 KB |
Output is correct |
| 3 |
Execution timed out |
1097 ms |
79380 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1097 ms |
78540 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1051 ms |
79164 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1101 ms |
78572 KB |
Time limit exceeded |
| 7 |
Correct |
683 ms |
78720 KB |
Output is correct |
| 8 |
Execution timed out |
1086 ms |
78536 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1097 ms |
79428 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1099 ms |
79404 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1100 ms |
79072 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1090 ms |
78548 KB |
Time limit exceeded |
| 13 |
Correct |
709 ms |
78612 KB |
Output is correct |
| 14 |
Execution timed out |
1100 ms |
78488 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1094 ms |
78972 KB |
Time limit exceeded |
| 16 |
Correct |
881 ms |
79664 KB |
Output is correct |
| 17 |
Execution timed out |
1087 ms |
78496 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1099 ms |
79736 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
79120 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1090 ms |
79160 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1097 ms |
79160 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1094 ms |
78608 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1056 ms |
80520 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1095 ms |
78636 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1062 ms |
79748 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1089 ms |
79052 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1098 ms |
79112 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1096 ms |
78604 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1089 ms |
78528 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1080 ms |
78588 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1092 ms |
78868 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1095 ms |
78548 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1060 ms |
78540 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1093 ms |
78548 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1097 ms |
79060 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1093 ms |
79180 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1041 ms |
78632 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1100 ms |
79180 KB |
Time limit exceeded |
| 21 |
Execution timed out |
1101 ms |
78548 KB |
Time limit exceeded |
| 22 |
Execution timed out |
1097 ms |
79648 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1080 ms |
79580 KB |
Time limit exceeded |
| 24 |
Correct |
616 ms |
78844 KB |
Output is correct |
| 25 |
Execution timed out |
1091 ms |
78564 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1102 ms |
78548 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1098 ms |
79752 KB |
Time limit exceeded |
| 28 |
Incorrect |
889 ms |
78836 KB |
Output isn't correct |
| 29 |
Execution timed out |
1101 ms |
79692 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1078 ms |
79308 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1077 ms |
78536 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1102 ms |
78548 KB |
Time limit exceeded |
| 33 |
Correct |
446 ms |
78840 KB |
Output is correct |
| 34 |
Execution timed out |
1100 ms |
79740 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1052 ms |
78924 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1101 ms |
79572 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1033 ms |
79876 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1093 ms |
78540 KB |
Time limit exceeded |
| 39 |
Correct |
784 ms |
78868 KB |
Output is correct |
| 40 |
Execution timed out |
1100 ms |
78640 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1081 ms |
79820 KB |
Time limit exceeded |
| 42 |
Execution timed out |
1102 ms |
78480 KB |
Time limit exceeded |
