oj.uz

Submission #558859

# Submission time Handle Problem Language Result Execution time Memory
558859 2022-05-08T19:34:44 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 1000 ms 135896 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;
        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
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 60768 KB Output is correct
2 Correct 738 ms 60688 KB Output is correct
3 Correct 615 ms 60676 KB Output is correct
4 Correct 584 ms 60612 KB Output is correct
5 Correct 605 ms 60680 KB Output is correct
6 Correct 580 ms 60696 KB Output is correct
7 Correct 660 ms 60624 KB Output is correct
8 Correct 679 ms 60680 KB Output is correct
9 Correct 734 ms 60688 KB Output is correct
10 Correct 805 ms 60584 KB Output is correct
11 Correct 832 ms 60684 KB Output is correct
12 Correct 663 ms 60744 KB Output is correct
13 Execution timed out 1102 ms 60672 KB Time limit exceeded
14 Execution timed out 1102 ms 60680 KB Time limit exceeded
15 Correct 791 ms 60740 KB Output is correct
16 Correct 721 ms 60688 KB Output is correct
17 Correct 674 ms 60716 KB Output is correct
18 Correct 597 ms 60644 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 760 ms 124288 KB Execution killed with signal 11
2 Runtime error 970 ms 134340 KB Execution killed with signal 11
3 Execution timed out 1064 ms 65320 KB Time limit exceeded
4 Runtime error 970 ms 123264 KB Execution killed with signal 11
5 Execution timed out 1072 ms 64152 KB Time limit exceeded
6 Runtime error 928 ms 122980 KB Execution killed with signal 11
7 Runtime error 860 ms 124460 KB Execution killed with signal 11
8 Runtime error 886 ms 122960 KB Execution killed with signal 11
9 Execution timed out 1084 ms 65788 KB Time limit exceeded
10 Execution timed out 1089 ms 65696 KB Time limit exceeded
11 Execution timed out 1085 ms 63400 KB Time limit exceeded
12 Execution timed out 1059 ms 123176 KB Time limit exceeded
13 Runtime error 831 ms 123248 KB Execution killed with signal 11
14 Runtime error 947 ms 123236 KB Execution killed with signal 11
15 Execution timed out 1089 ms 63556 KB Time limit exceeded
16 Runtime error 956 ms 134792 KB Execution killed with signal 11
17 Execution timed out 1063 ms 60772 KB Time limit exceeded
18 Execution timed out 1074 ms 67296 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 64152 KB Time limit exceeded
2 Execution timed out 1095 ms 64292 KB Time limit exceeded
3 Execution timed out 1093 ms 64252 KB Time limit exceeded
4 Execution timed out 1050 ms 123392 KB Time limit exceeded
5 Runtime error 876 ms 135896 KB Execution killed with signal 11
6 Execution timed out 1096 ms 61316 KB Time limit exceeded
7 Execution timed out 1088 ms 67424 KB Time limit exceeded
8 Execution timed out 1094 ms 64200 KB Time limit exceeded
9 Execution timed out 1100 ms 64208 KB Time limit exceeded
10 Execution timed out 1016 ms 123740 KB Time limit exceeded
11 Runtime error 916 ms 123544 KB Execution killed with signal 11
12 Execution timed out 1090 ms 61160 KB Time limit exceeded
13 Execution timed out 1097 ms 62756 KB Time limit exceeded
14 Runtime error 770 ms 122888 KB Execution killed with signal 11
15 Execution timed out 1098 ms 61184 KB Time limit exceeded
16 Execution timed out 1100 ms 61280 KB Time limit exceeded
17 Execution timed out 1090 ms 63868 KB Time limit exceeded
18 Execution timed out 1095 ms 64300 KB Time limit exceeded
19 Runtime error 769 ms 123612 KB Execution killed with signal 11
20 Execution timed out 1101 ms 64276 KB Time limit exceeded
21 Runtime error 922 ms 122764 KB Execution killed with signal 11
22 Execution timed out 1102 ms 66896 KB Time limit exceeded
23 Runtime error 761 ms 126444 KB Execution killed with signal 11
24 Runtime error 680 ms 122956 KB Execution killed with signal 11
25 Execution timed out 1012 ms 123192 KB Time limit exceeded
26 Runtime error 984 ms 123348 KB Execution killed with signal 11
27 Execution timed out 1097 ms 66764 KB Time limit exceeded
28 Runtime error 686 ms 122996 KB Execution killed with signal 11
29 Execution timed out 1101 ms 66764 KB Time limit exceeded
30 Execution timed out 1102 ms 65220 KB Time limit exceeded
31 Runtime error 775 ms 123464 KB Execution killed with signal 11
32 Runtime error 816 ms 123184 KB Execution killed with signal 11
33 Runtime error 660 ms 122972 KB Execution killed with signal 11
34 Execution timed out 1099 ms 66740 KB Time limit exceeded
35 Runtime error 769 ms 123128 KB Execution killed with signal 11
36 Execution timed out 1096 ms 66252 KB Time limit exceeded
37 Runtime error 852 ms 135104 KB Execution killed with signal 11
38 Execution timed out 1104 ms 61120 KB Time limit exceeded
39 Runtime error 761 ms 123212 KB Execution killed with signal 11
40 Execution timed out 1094 ms 61200 KB Time limit exceeded
41 Execution timed out 1094 ms 66764 KB Time limit exceeded
42 Execution timed out 1057 ms 60744 KB Time limit exceeded