oj.uz

Submission #558862

# Submission time Handle Problem Language Result Execution time Memory
558862 2022-05-08T19:38:16 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 1000 ms 125256 KB 
#include <bits/stdc++.h>
using namespace std;
template<class T>
class SegmentTree {
public:
 
    SegmentTree (int N) {
        N = (1 << ((int)floor(log2(N - 1)) + 1));
        this->N = N;
        val.assign(2 * N, ID);
    }
 
    void update (int x, T y) {
        x += N - 1;
        val[x] = y;
        while (x != 0) {
            x = (x - 1)/2;
            val[x] = merge(val[2 * x + 1], val[2 * x + 2]);
        }
    }
 
    T query (int ind, const int l, const int r, int tl, int tr) {
        if (tl >= l && tr <= r) {
            return val[ind];
        }
        if (tr < l || tl > r) {
            return ID;
        }
        return merge(query(2 * ind + 1, l, r, tl, (tl + tr)/2), query(2 * ind + 2, l, r, (tl + tr)/2 + 1, tr));
    }
 
    T query (int l, int r) {
        return query(0, l, r, 0, N - 1);
    }
private:
    vector<T> val;
    T ID = 1e9;
    T merge (T x, T y) {
        return min(x, y);
    }
    int N;
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int M, Q; cin >> M >> Q;
    vector<int> p(M);
    SegmentTree<int> st(M);
    map<int,int> primes;
    for (int i = 0; i < M; i++) {
        cin >> p[i];
        st.update(i, 0);
    }
    sort(p.begin(), p.end());
    for (int i = 0; i < M; i++) {
        primes[p[i]] = i;
        st.update(i, 0);
    } 
    int mx = 1000000;
    int res[mx];
    bool isPrime[mx];
    for (int i = 0; i < mx; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    vector<int> fact[mx];
    for (int i = 2; i < mx; i++) {
        if (isPrime[i]) {
            for (int j = 2 * i; j < mx; j += i) {
                isPrime[j] = false;
                if (primes.count(i)) fact[j].push_back(i);
            }
            if (primes.count(i)) fact[i].push_back(i);
        }
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        vector<int> invalid;
        invalid.push_back(-1);
        for (int j: fact[i]) {
            invalid.push_back(primes[j]);
        }
        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.update(j, ans);
            }
        }
        res[i] = ans;
    }
    while (Q--) {
        int x;
        cin >> x;
        if (res[x] == (int)1e9) {
            cout << "oo\n";
        } else {
            cout << res[x] << '\n';
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 33960 KB Output is correct
2 Correct 345 ms 51444 KB Output is correct
3 Correct 230 ms 48248 KB Output is correct
4 Correct 217 ms 31116 KB Output is correct
5 Correct 227 ms 36916 KB Output is correct
6 Correct 156 ms 33928 KB Output is correct
7 Correct 246 ms 48236 KB Output is correct
8 Correct 294 ms 52212 KB Output is correct
9 Correct 325 ms 54304 KB Output is correct
10 Correct 443 ms 55280 KB Output is correct
11 Correct 372 ms 50636 KB Output is correct
12 Correct 168 ms 30284 KB Output is correct
13 Correct 944 ms 58228 KB Output is correct
14 Correct 946 ms 58228 KB Output is correct
15 Correct 340 ms 50724 KB Output is correct
16 Correct 323 ms 51456 KB Output is correct
17 Correct 241 ms 36800 KB Output is correct
18 Correct 167 ms 31036 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 342 ms 70052 KB Execution killed with signal 11
2 Runtime error 445 ms 82436 KB Execution killed with signal 11
3 Execution timed out 1099 ms 64788 KB Time limit exceeded
4 Runtime error 480 ms 84812 KB Execution killed with signal 11
5 Runtime error 827 ms 117096 KB Execution killed with signal 11
6 Runtime error 393 ms 96244 KB Execution killed with signal 11
7 Runtime error 338 ms 69968 KB Execution killed with signal 11
8 Runtime error 364 ms 81540 KB Execution killed with signal 11
9 Execution timed out 1065 ms 124808 KB Time limit exceeded
10 Execution timed out 1097 ms 64816 KB Time limit exceeded
11 Execution timed out 1085 ms 61668 KB Time limit exceeded
12 Runtime error 620 ms 106956 KB Execution killed with signal 11
13 Runtime error 319 ms 74132 KB Execution killed with signal 11
14 Runtime error 465 ms 84804 KB Execution killed with signal 11
15 Execution timed out 1088 ms 60872 KB Time limit exceeded
16 Runtime error 467 ms 82512 KB Execution killed with signal 11
17 Execution timed out 1034 ms 117260 KB Time limit exceeded
18 Execution timed out 1081 ms 63372 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 61928 KB Time limit exceeded
2 Execution timed out 1065 ms 62788 KB Time limit exceeded
3 Execution timed out 1087 ms 62732 KB Time limit exceeded
4 Runtime error 762 ms 108932 KB Execution killed with signal 11
5 Runtime error 594 ms 82880 KB Execution killed with signal 11
6 Execution timed out 1072 ms 115140 KB Time limit exceeded
7 Runtime error 979 ms 116380 KB Execution killed with signal 11
8 Execution timed out 1099 ms 61860 KB Time limit exceeded
9 Execution timed out 1083 ms 61872 KB Time limit exceeded
10 Runtime error 838 ms 104832 KB Execution killed with signal 11
11 Runtime error 686 ms 97492 KB Execution killed with signal 11
12 Execution timed out 1067 ms 114848 KB Time limit exceeded
13 Execution timed out 1096 ms 60132 KB Time limit exceeded
14 Runtime error 547 ms 113240 KB Execution killed with signal 11
15 Execution timed out 1081 ms 58096 KB Time limit exceeded
16 Execution timed out 1079 ms 58584 KB Time limit exceeded
17 Execution timed out 1088 ms 58952 KB Time limit exceeded
18 Execution timed out 1082 ms 62772 KB Time limit exceeded
19 Runtime error 433 ms 85292 KB Execution killed with signal 11
20 Execution timed out 1087 ms 62688 KB Time limit exceeded
21 Runtime error 731 ms 115968 KB Execution killed with signal 11
22 Execution timed out 1081 ms 66024 KB Time limit exceeded
23 Runtime error 457 ms 78584 KB Execution killed with signal 11
24 Runtime error 326 ms 69868 KB Execution killed with signal 11
25 Runtime error 807 ms 107288 KB Execution killed with signal 11
26 Runtime error 721 ms 109020 KB Execution killed with signal 11
27 Execution timed out 1089 ms 66716 KB Time limit exceeded
28 Runtime error 330 ms 80524 KB Execution killed with signal 11
29 Execution timed out 1102 ms 109300 KB Time limit exceeded
30 Runtime error 997 ms 125256 KB Execution killed with signal 11
31 Runtime error 397 ms 83084 KB Execution killed with signal 11
32 Runtime error 452 ms 89324 KB Execution killed with signal 11
33 Runtime error 234 ms 64868 KB Execution killed with signal 11
34 Runtime error 898 ms 116384 KB Execution killed with signal 11
35 Runtime error 357 ms 81996 KB Execution killed with signal 11
36 Execution timed out 1088 ms 65356 KB Time limit exceeded
37 Runtime error 521 ms 82872 KB Execution killed with signal 11
38 Runtime error 989 ms 115648 KB Execution killed with signal 11
39 Runtime error 389 ms 73500 KB Execution killed with signal 11
40 Runtime error 896 ms 113352 KB Execution killed with signal 11
41 Runtime error 878 ms 120932 KB Execution killed with signal 11
42 Execution timed out 1063 ms 58352 KB Time limit exceeded