oj.uz

Submission #558861

# Submission time Handle Problem Language Result Execution time Memory
558861 2022-05-08T19:37:44 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 1000 ms 135252 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;
                fact[j].push_back(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]) {
            if (primes.count(j)) 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
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 60704 KB Output is correct
2 Correct 617 ms 60692 KB Output is correct
3 Correct 590 ms 60740 KB Output is correct
4 Correct 534 ms 60736 KB Output is correct
5 Correct 571 ms 60632 KB Output is correct
6 Correct 523 ms 60720 KB Output is correct
7 Correct 564 ms 60684 KB Output is correct
8 Correct 600 ms 60684 KB Output is correct
9 Correct 621 ms 60796 KB Output is correct
10 Correct 675 ms 60696 KB Output is correct
11 Correct 651 ms 60824 KB Output is correct
12 Correct 565 ms 60680 KB Output is correct
13 Execution timed out 1035 ms 60796 KB Time limit exceeded
14 Execution timed out 1012 ms 60788 KB Time limit exceeded
15 Correct 654 ms 60688 KB Output is correct
16 Correct 627 ms 60592 KB Output is correct
17 Correct 607 ms 60764 KB Output is correct
18 Correct 520 ms 60876 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 672 ms 124376 KB Execution killed with signal 11
2 Runtime error 802 ms 134856 KB Execution killed with signal 11
3 Execution timed out 1082 ms 65692 KB Time limit exceeded
4 Runtime error 776 ms 123232 KB Execution killed with signal 11
5 Execution timed out 1061 ms 129224 KB Time limit exceeded
6 Runtime error 730 ms 122980 KB Execution killed with signal 11
7 Runtime error 637 ms 124416 KB Execution killed with signal 11
8 Runtime error 674 ms 122948 KB Execution killed with signal 11
9 Execution timed out 1087 ms 65324 KB Time limit exceeded
10 Execution timed out 1055 ms 65208 KB Time limit exceeded
11 Execution timed out 1090 ms 63184 KB Time limit exceeded
12 Runtime error 861 ms 123104 KB Execution killed with signal 11
13 Runtime error 683 ms 123208 KB Execution killed with signal 11
14 Runtime error 817 ms 123212 KB Execution killed with signal 11
15 Execution timed out 1090 ms 63248 KB Time limit exceeded
16 Runtime error 898 ms 134348 KB Execution killed with signal 11
17 Execution timed out 1096 ms 60864 KB Time limit exceeded
18 Execution timed out 1070 ms 66744 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 63684 KB Time limit exceeded
2 Execution timed out 1094 ms 63820 KB Time limit exceeded
3 Execution timed out 1080 ms 63684 KB Time limit exceeded
4 Runtime error 968 ms 123192 KB Execution killed with signal 11
5 Runtime error 834 ms 135252 KB Execution killed with signal 11
6 Execution timed out 1101 ms 86500 KB Time limit exceeded
7 Execution timed out 1098 ms 106616 KB Time limit exceeded
8 Execution timed out 1086 ms 63820 KB Time limit exceeded
9 Execution timed out 1093 ms 63748 KB Time limit exceeded
10 Runtime error 996 ms 123592 KB Execution killed with signal 11
11 Runtime error 918 ms 123436 KB Execution killed with signal 11
12 Execution timed out 1102 ms 90752 KB Time limit exceeded
13 Execution timed out 1072 ms 62528 KB Time limit exceeded
14 Runtime error 691 ms 122884 KB Execution killed with signal 11
15 Execution timed out 1100 ms 61004 KB Time limit exceeded
16 Execution timed out 1097 ms 61048 KB Time limit exceeded
17 Execution timed out 1096 ms 63472 KB Time limit exceeded
18 Execution timed out 1097 ms 63772 KB Time limit exceeded
19 Runtime error 778 ms 123468 KB Execution killed with signal 11
20 Execution timed out 1095 ms 63668 KB Time limit exceeded
21 Runtime error 929 ms 122768 KB Execution killed with signal 11
22 Execution timed out 1100 ms 66756 KB Time limit exceeded
23 Runtime error 915 ms 126472 KB Execution killed with signal 11
24 Runtime error 795 ms 122968 KB Execution killed with signal 11
25 Execution timed out 1052 ms 123204 KB Time limit exceeded
26 Execution timed out 1014 ms 123260 KB Time limit exceeded
27 Execution timed out 1088 ms 66864 KB Time limit exceeded
28 Runtime error 842 ms 122988 KB Execution killed with signal 11
29 Execution timed out 1080 ms 66864 KB Time limit exceeded
30 Execution timed out 1087 ms 65216 KB Time limit exceeded
31 Runtime error 858 ms 123368 KB Execution killed with signal 11
32 Runtime error 920 ms 123212 KB Execution killed with signal 11
33 Runtime error 720 ms 122972 KB Execution killed with signal 11
34 Execution timed out 1093 ms 66796 KB Time limit exceeded
35 Runtime error 795 ms 123012 KB Execution killed with signal 11
36 Execution timed out 1072 ms 66212 KB Time limit exceeded
37 Runtime error 903 ms 135104 KB Execution killed with signal 11
38 Execution timed out 1093 ms 61064 KB Time limit exceeded
39 Runtime error 803 ms 123176 KB Execution killed with signal 11
40 Execution timed out 1042 ms 61260 KB Time limit exceeded
41 Execution timed out 1079 ms 66696 KB Time limit exceeded
42 Execution timed out 1088 ms 60776 KB Time limit exceeded