oj.uz

Submission #558857

# Submission time Handle Problem Language Result Execution time Memory
558857 2022-05-08T19:33:22 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 196 ms 25260 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() {
    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 = 100000;
    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;
                fact[j].push_back(i);
            }
            fact[i].push_back(i);
        }
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        set<int> invalid;
        for (int j: fact[i]) {
            if (primes.count(j)) {
                invalid.insert(primes[j]);
            }
        }
        invalid.insert(-1);
        invalid.insert(p.size());
        for (int j: invalid) {
            auto it = invalid.upper_bound(j);
            if (it == invalid.end()) continue;
            if (j + 1 <= *it - 1) {
                ans = min(ans, st.query(j + 1, *it - 1) + 1);
            }
        }
        invalid.erase(-1), invalid.erase(p.size());
        for (int j: invalid) {
            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 54 ms 6228 KB Output is correct
2 Correct 64 ms 6276 KB Output is correct
3 Correct 41 ms 6324 KB Output is correct
4 Correct 54 ms 6328 KB Output is correct
5 Correct 34 ms 6188 KB Output is correct
6 Correct 36 ms 6280 KB Output is correct
7 Correct 42 ms 6228 KB Output is correct
8 Correct 45 ms 6228 KB Output is correct
9 Correct 55 ms 6228 KB Output is correct
10 Correct 77 ms 6280 KB Output is correct
11 Correct 61 ms 6228 KB Output is correct
12 Correct 38 ms 6292 KB Output is correct
13 Correct 98 ms 6332 KB Output is correct
14 Correct 102 ms 6380 KB Output is correct
15 Correct 51 ms 6276 KB Output is correct
16 Correct 61 ms 6288 KB Output is correct
17 Correct 66 ms 6296 KB Output is correct
18 Correct 51 ms 6340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 14152 KB Execution killed with signal 11
2 Runtime error 125 ms 24212 KB Execution killed with signal 11
3 Runtime error 182 ms 22104 KB Execution killed with signal 11
4 Runtime error 65 ms 12880 KB Execution killed with signal 11
5 Runtime error 115 ms 19136 KB Execution killed with signal 11
6 Runtime error 59 ms 12628 KB Execution killed with signal 11
7 Runtime error 63 ms 14144 KB Execution killed with signal 11
8 Runtime error 62 ms 12604 KB Execution killed with signal 11
9 Runtime error 137 ms 22204 KB Execution killed with signal 11
10 Runtime error 168 ms 22016 KB Execution killed with signal 11
11 Runtime error 142 ms 17872 KB Execution killed with signal 11
12 Runtime error 76 ms 12820 KB Execution killed with signal 11
13 Runtime error 50 ms 12872 KB Execution killed with signal 11
14 Runtime error 66 ms 13004 KB Execution killed with signal 11
15 Runtime error 153 ms 18084 KB Execution killed with signal 11
16 Runtime error 128 ms 24288 KB Execution killed with signal 11
17 Runtime error 103 ms 12872 KB Execution killed with signal 11
18 Runtime error 163 ms 25088 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 19060 KB Execution killed with signal 11
2 Runtime error 164 ms 19208 KB Execution killed with signal 11
3 Runtime error 153 ms 18892 KB Execution killed with signal 11
4 Runtime error 75 ms 12984 KB Execution killed with signal 11
5 Runtime error 118 ms 25000 KB Execution killed with signal 11
6 Runtime error 124 ms 13644 KB Execution killed with signal 11
7 Runtime error 149 ms 25228 KB Execution killed with signal 11
8 Runtime error 130 ms 18952 KB Execution killed with signal 11
9 Runtime error 144 ms 18972 KB Execution killed with signal 11
10 Runtime error 89 ms 13288 KB Execution killed with signal 11
11 Runtime error 70 ms 13208 KB Execution killed with signal 11
12 Runtime error 98 ms 13404 KB Execution killed with signal 11
13 Runtime error 130 ms 16400 KB Execution killed with signal 11
14 Runtime error 72 ms 12576 KB Execution killed with signal 11
15 Runtime error 109 ms 13256 KB Execution killed with signal 11
16 Runtime error 109 ms 13460 KB Execution killed with signal 11
17 Runtime error 117 ms 18420 KB Execution killed with signal 11
18 Runtime error 161 ms 19160 KB Execution killed with signal 11
19 Runtime error 66 ms 13236 KB Execution killed with signal 11
20 Runtime error 145 ms 19028 KB Execution killed with signal 11
21 Runtime error 69 ms 12492 KB Execution killed with signal 11
22 Runtime error 179 ms 25260 KB Execution killed with signal 11
23 Runtime error 67 ms 16352 KB Execution killed with signal 11
24 Runtime error 59 ms 12748 KB Execution killed with signal 11
25 Runtime error 93 ms 12960 KB Execution killed with signal 11
26 Runtime error 74 ms 12988 KB Execution killed with signal 11
27 Runtime error 192 ms 25188 KB Execution killed with signal 11
28 Runtime error 52 ms 12656 KB Execution killed with signal 11
29 Runtime error 196 ms 25104 KB Execution killed with signal 11
30 Runtime error 128 ms 21980 KB Execution killed with signal 11
31 Runtime error 55 ms 13112 KB Execution killed with signal 11
32 Runtime error 58 ms 12936 KB Execution killed with signal 11
33 Runtime error 52 ms 12668 KB Execution killed with signal 11
34 Runtime error 164 ms 25212 KB Execution killed with signal 11
35 Runtime error 51 ms 12836 KB Execution killed with signal 11
36 Runtime error 176 ms 24008 KB Execution killed with signal 11
37 Runtime error 138 ms 25004 KB Execution killed with signal 11
38 Runtime error 134 ms 13700 KB Execution killed with signal 11
39 Runtime error 54 ms 12924 KB Execution killed with signal 11
40 Runtime error 89 ms 13916 KB Execution killed with signal 11
41 Runtime error 145 ms 25192 KB Execution killed with signal 11
42 Runtime error 126 ms 12968 KB Execution killed with signal 11