oj.uz

Submission #558858

# Submission time Handle Problem Language Result Execution time Memory
558858 2022-05-08T19:34:06 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 1000 ms 135540 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 = 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 554 ms 60892 KB Output is correct
2 Correct 666 ms 60752 KB Output is correct
3 Correct 615 ms 60712 KB Output is correct
4 Correct 594 ms 60676 KB Output is correct
5 Correct 587 ms 60620 KB Output is correct
6 Correct 568 ms 60584 KB Output is correct
7 Correct 597 ms 60660 KB Output is correct
8 Correct 617 ms 60660 KB Output is correct
9 Correct 671 ms 60728 KB Output is correct
10 Correct 717 ms 60628 KB Output is correct
11 Correct 693 ms 60652 KB Output is correct
12 Correct 561 ms 60664 KB Output is correct
13 Execution timed out 1072 ms 60608 KB Time limit exceeded
14 Execution timed out 1097 ms 60724 KB Time limit exceeded
15 Correct 649 ms 60632 KB Output is correct
16 Correct 655 ms 60720 KB Output is correct
17 Correct 648 ms 60720 KB Output is correct
18 Correct 572 ms 60620 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 683 ms 124308 KB Execution killed with signal 11
2 Runtime error 824 ms 134428 KB Execution killed with signal 11
3 Execution timed out 1095 ms 65328 KB Time limit exceeded
4 Runtime error 768 ms 123288 KB Execution killed with signal 11
5 Execution timed out 1057 ms 84696 KB Time limit exceeded
6 Runtime error 721 ms 122916 KB Execution killed with signal 11
7 Runtime error 697 ms 124304 KB Execution killed with signal 11
8 Runtime error 707 ms 122932 KB Execution killed with signal 11
9 Execution timed out 1057 ms 65316 KB Time limit exceeded
10 Execution timed out 1102 ms 65228 KB Time limit exceeded
11 Execution timed out 1063 ms 63200 KB Time limit exceeded
12 Runtime error 879 ms 123000 KB Execution killed with signal 11
13 Runtime error 687 ms 123184 KB Execution killed with signal 11
14 Runtime error 775 ms 123168 KB Execution killed with signal 11
15 Execution timed out 1101 ms 63320 KB Time limit exceeded
16 Runtime error 841 ms 134316 KB Execution killed with signal 11
17 Execution timed out 1099 ms 60772 KB Time limit exceeded
18 Execution timed out 1087 ms 66712 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 63700 KB Time limit exceeded
2 Execution timed out 1058 ms 63780 KB Time limit exceeded
3 Execution timed out 1091 ms 63692 KB Time limit exceeded
4 Execution timed out 1036 ms 123200 KB Time limit exceeded
5 Runtime error 930 ms 135080 KB Execution killed with signal 11
6 Execution timed out 1097 ms 61040 KB Time limit exceeded
7 Execution timed out 1101 ms 66736 KB Time limit exceeded
8 Execution timed out 1095 ms 63716 KB Time limit exceeded
9 Execution timed out 1088 ms 63720 KB Time limit exceeded
10 Execution timed out 1098 ms 60952 KB Time limit exceeded
11 Runtime error 991 ms 123308 KB Execution killed with signal 11
12 Execution timed out 1103 ms 60980 KB Time limit exceeded
13 Execution timed out 1053 ms 62388 KB Time limit exceeded
14 Runtime error 870 ms 122900 KB Execution killed with signal 11
15 Execution timed out 1090 ms 60896 KB Time limit exceeded
16 Execution timed out 1096 ms 61004 KB Time limit exceeded
17 Execution timed out 1099 ms 63396 KB Time limit exceeded
18 Execution timed out 1095 ms 63744 KB Time limit exceeded
19 Runtime error 875 ms 123424 KB Execution killed with signal 11
20 Execution timed out 1082 ms 63660 KB Time limit exceeded
21 Execution timed out 1088 ms 104100 KB Time limit exceeded
22 Execution timed out 1039 ms 67220 KB Time limit exceeded
23 Runtime error 945 ms 126824 KB Execution killed with signal 11
24 Runtime error 824 ms 122952 KB Execution killed with signal 11
25 Execution timed out 1079 ms 60896 KB Time limit exceeded
26 Execution timed out 1101 ms 95932 KB Time limit exceeded
27 Execution timed out 1067 ms 67236 KB Time limit exceeded
28 Runtime error 806 ms 122892 KB Execution killed with signal 11
29 Execution timed out 1098 ms 67364 KB Time limit exceeded
30 Execution timed out 1098 ms 65788 KB Time limit exceeded
31 Runtime error 915 ms 123524 KB Execution killed with signal 11
32 Runtime error 920 ms 123280 KB Execution killed with signal 11
33 Runtime error 700 ms 122984 KB Execution killed with signal 11
34 Execution timed out 1086 ms 67468 KB Time limit exceeded
35 Runtime error 847 ms 123056 KB Execution killed with signal 11
36 Execution timed out 1088 ms 66772 KB Time limit exceeded
37 Runtime error 1000 ms 135540 KB Execution killed with signal 11
38 Execution timed out 1086 ms 61292 KB Time limit exceeded
39 Runtime error 765 ms 123188 KB Execution killed with signal 11
40 Execution timed out 1098 ms 65368 KB Time limit exceeded
41 Execution timed out 1089 ms 67264 KB Time limit exceeded
42 Execution timed out 1096 ms 60872 KB Time limit exceeded