oj.uz

Submission #558855

# Submission time Handle Problem Language Result Execution time Memory
558855 2022-05-08T19:30:05 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 80 ms 13680 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 = 10;
    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);
        }
        //cout << i << " < - > " << ans << '\n';
        res[i] = ans;
    }
    while (Q--) {
        int x;
        cin >> x;
        if (res[x] == (int)1e9) {
            cout << "oo\n";
        } else {
            cout << res[x] << '\n';
        }
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Runtime error 3 ms 468 KB Execution killed with signal 11
5 Incorrect 1 ms 212 KB Output isn't correct
6 Runtime error 1 ms 340 KB Execution killed with signal 11
7 Runtime error 1 ms 340 KB Execution killed with signal 11
8 Runtime error 1 ms 304 KB Execution killed with signal 11
9 Incorrect 1 ms 212 KB Output isn't correct
10 Runtime error 1 ms 340 KB Execution killed with signal 11
11 Runtime error 1 ms 304 KB Execution killed with signal 11
12 Runtime error 1 ms 340 KB Execution killed with signal 11
13 Runtime error 2 ms 440 KB Execution killed with signal 11
14 Runtime error 2 ms 568 KB Execution killed with signal 11
15 Runtime error 1 ms 340 KB Execution killed with signal 11
16 Runtime error 1 ms 340 KB Execution killed with signal 11
17 Runtime error 2 ms 468 KB Execution killed with signal 11
18 Runtime error 2 ms 368 KB Execution killed with signal 11

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2004 KB Execution killed with signal 11
2 Runtime error 60 ms 12552 KB Execution killed with signal 11
3 Runtime error 45 ms 10164 KB Execution killed with signal 11
4 Runtime error 2 ms 724 KB Execution killed with signal 11
5 Runtime error 32 ms 7012 KB Execution killed with signal 11
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Runtime error 8 ms 2004 KB Execution killed with signal 11
8 Runtime error 1 ms 468 KB Execution killed with signal 11
9 Runtime error 45 ms 10292 KB Execution killed with signal 11
10 Runtime error 43 ms 10176 KB Execution killed with signal 11
11 Runtime error 26 ms 5836 KB Execution killed with signal 11
12 Runtime error 2 ms 596 KB Execution killed with signal 11
13 Runtime error 3 ms 700 KB Execution killed with signal 11
14 Runtime error 2 ms 724 KB Execution killed with signal 11
15 Runtime error 27 ms 5964 KB Execution killed with signal 11
16 Runtime error 63 ms 12560 KB Execution killed with signal 11
17 Runtime error 2 ms 724 KB Execution killed with signal 11
18 Runtime error 68 ms 13472 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 7156 KB Execution killed with signal 11
2 Runtime error 33 ms 7244 KB Execution killed with signal 11
3 Runtime error 34 ms 7060 KB Execution killed with signal 11
4 Runtime error 3 ms 852 KB Execution killed with signal 11
5 Runtime error 69 ms 13596 KB Execution killed with signal 11
6 Runtime error 7 ms 1592 KB Execution killed with signal 11
7 Runtime error 65 ms 13588 KB Execution killed with signal 11
8 Runtime error 34 ms 7016 KB Execution killed with signal 11
9 Runtime error 30 ms 6988 KB Execution killed with signal 11
10 Runtime error 4 ms 1236 KB Execution killed with signal 11
11 Runtime error 3 ms 1084 KB Execution killed with signal 11
12 Runtime error 4 ms 1236 KB Execution killed with signal 11
13 Runtime error 23 ms 4308 KB Execution killed with signal 11
14 Runtime error 1 ms 468 KB Execution killed with signal 11
15 Runtime error 3 ms 1108 KB Execution killed with signal 11
16 Runtime error 4 ms 1364 KB Execution killed with signal 11
17 Runtime error 30 ms 6480 KB Execution killed with signal 11
18 Runtime error 33 ms 7288 KB Execution killed with signal 11
19 Runtime error 4 ms 1108 KB Execution killed with signal 11
20 Runtime error 36 ms 7068 KB Execution killed with signal 11
21 Runtime error 1 ms 468 KB Execution killed with signal 11
22 Runtime error 64 ms 13604 KB Execution killed with signal 11
23 Runtime error 18 ms 4384 KB Execution killed with signal 11
24 Runtime error 2 ms 596 KB Execution killed with signal 11
25 Runtime error 3 ms 828 KB Execution killed with signal 11
26 Runtime error 3 ms 836 KB Execution killed with signal 11
27 Runtime error 80 ms 13680 KB Execution killed with signal 11
28 Runtime error 1 ms 572 KB Execution killed with signal 11
29 Runtime error 65 ms 13604 KB Execution killed with signal 11
30 Runtime error 49 ms 10296 KB Execution killed with signal 11
31 Runtime error 4 ms 1140 KB Execution killed with signal 11
32 Runtime error 3 ms 828 KB Execution killed with signal 11
33 Runtime error 1 ms 596 KB Execution killed with signal 11
34 Runtime error 62 ms 13616 KB Execution killed with signal 11
35 Runtime error 2 ms 596 KB Execution killed with signal 11
36 Runtime error 61 ms 12672 KB Execution killed with signal 11
37 Runtime error 67 ms 13560 KB Execution killed with signal 11
38 Runtime error 5 ms 1620 KB Execution killed with signal 11
39 Runtime error 2 ms 824 KB Execution killed with signal 11
40 Runtime error 7 ms 1844 KB Execution killed with signal 11
41 Runtime error 63 ms 13676 KB Execution killed with signal 11
42 Runtime error 2 ms 852 KB Execution killed with signal 11