oj.uz

Submission #558883

# Submission time Handle Problem Language Result Execution time Memory
558883 2022-05-08T23:11:43 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
11.1111 / 100
 123 ms 24448 KB 
#include <bits/stdc++.h>
using namespace std;
template<class T> struct Seg { // comb(ID,b) = b
	const T ID = 1e9; T comb(T a, T b) { return min(a,b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// min on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int M, Q; cin >> M >> Q;
    vector<int> p(M);
    Seg<int> st;
    st.init(M + 1);
    map<int,int> primes;
    for (int i = 0; i < M; i++) {
        cin >> p[i];
        st.upd(i, 0);
    }
    sort(p.begin(), p.end());
    for (int i = 0; i < M; i++) {
        primes[p[i]] = i;
        st.upd(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;
                if (primes.count(i)) fact[j].push_back(primes[i]);
            }
            if (primes.count(i)) fact[i].push_back(primes[i]);
        }
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        vector<int> invalid;
        invalid.push_back(-1);
        for (int j: fact[i]) {
            invalid.push_back(j);
        }
        invalid.push_back(p.size());
        for (int j = 0; j < min((int)invalid.size() - 1, (int)2); 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 = max(0, (int)invalid.size() - 2); 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.upd(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
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3616 KB Output is correct
2 Incorrect 22 ms 5432 KB Output isn't correct
3 Incorrect 22 ms 5044 KB Output isn't correct
4 Correct 16 ms 3392 KB Output is correct
5 Correct 14 ms 3972 KB Output is correct
6 Correct 14 ms 3688 KB Output is correct
7 Incorrect 17 ms 5076 KB Output isn't correct
8 Incorrect 23 ms 5460 KB Output isn't correct
9 Correct 29 ms 5716 KB Output is correct
10 Incorrect 25 ms 5716 KB Output isn't correct
11 Incorrect 23 ms 5344 KB Output isn't correct
12 Correct 12 ms 3328 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 51 ms 6076 KB Output is correct
15 Incorrect 24 ms 5332 KB Output isn't correct
16 Incorrect 25 ms 5392 KB Output isn't correct
17 Correct 18 ms 3924 KB Output is correct
18 Correct 14 ms 3412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 8416 KB Execution killed with signal 11
2 Runtime error 63 ms 18156 KB Execution killed with signal 11
3 Runtime error 93 ms 20812 KB Execution killed with signal 11
4 Runtime error 40 ms 9272 KB Execution killed with signal 11
5 Runtime error 90 ms 17400 KB Execution killed with signal 11
6 Runtime error 26 ms 10060 KB Execution killed with signal 11
7 Runtime error 26 ms 8512 KB Execution killed with signal 11
8 Runtime error 28 ms 8700 KB Execution killed with signal 11
9 Runtime error 85 ms 20228 KB Execution killed with signal 11
10 Runtime error 101 ms 20740 KB Execution killed with signal 11
11 Runtime error 91 ms 17276 KB Execution killed with signal 11
12 Runtime error 35 ms 11348 KB Execution killed with signal 11
13 Runtime error 22 ms 8012 KB Execution killed with signal 11
14 Runtime error 30 ms 9208 KB Execution killed with signal 11
15 Runtime error 68 ms 17132 KB Execution killed with signal 11
16 Runtime error 63 ms 18164 KB Execution killed with signal 11
17 Runtime error 68 ms 12380 KB Execution killed with signal 11
18 Runtime error 100 ms 23668 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 18160 KB Execution killed with signal 11
2 Runtime error 88 ms 18692 KB Execution killed with signal 11
3 Runtime error 100 ms 18520 KB Execution killed with signal 11
4 Runtime error 43 ms 11724 KB Execution killed with signal 11
5 Runtime error 68 ms 18780 KB Execution killed with signal 11
6 Runtime error 50 ms 13084 KB Execution killed with signal 11
7 Runtime error 89 ms 22428 KB Execution killed with signal 11
8 Runtime error 77 ms 18176 KB Execution killed with signal 11
9 Runtime error 83 ms 18160 KB Execution killed with signal 11
10 Runtime error 46 ms 11860 KB Execution killed with signal 11
11 Runtime error 35 ms 10828 KB Execution killed with signal 11
12 Runtime error 48 ms 12728 KB Execution killed with signal 11
13 Runtime error 73 ms 15924 KB Execution killed with signal 11
14 Runtime error 32 ms 11724 KB Execution killed with signal 11
15 Runtime error 65 ms 12872 KB Execution killed with signal 11
16 Runtime error 71 ms 13180 KB Execution killed with signal 11
17 Runtime error 63 ms 16972 KB Execution killed with signal 11
18 Runtime error 79 ms 18700 KB Execution killed with signal 11
19 Runtime error 31 ms 9336 KB Execution killed with signal 11
20 Runtime error 84 ms 18452 KB Execution killed with signal 11
21 Runtime error 39 ms 11844 KB Execution killed with signal 11
22 Runtime error 112 ms 24324 KB Execution killed with signal 11
23 Runtime error 35 ms 10912 KB Execution killed with signal 11
24 Runtime error 21 ms 7508 KB Execution killed with signal 11
25 Runtime error 41 ms 11608 KB Execution killed with signal 11
26 Runtime error 38 ms 11792 KB Execution killed with signal 11
27 Runtime error 107 ms 24448 KB Execution killed with signal 11
28 Runtime error 26 ms 8540 KB Execution killed with signal 11
29 Runtime error 99 ms 23956 KB Execution killed with signal 11
30 Runtime error 78 ms 19968 KB Execution killed with signal 11
31 Runtime error 26 ms 9036 KB Execution killed with signal 11
32 Runtime error 32 ms 9664 KB Execution killed with signal 11
33 Runtime error 20 ms 7004 KB Execution killed with signal 11
34 Runtime error 91 ms 22348 KB Execution killed with signal 11
35 Runtime error 33 ms 8812 KB Execution killed with signal 11
36 Runtime error 123 ms 23160 KB Execution killed with signal 11
37 Runtime error 65 ms 18740 KB Execution killed with signal 11
38 Runtime error 56 ms 13132 KB Execution killed with signal 11
39 Runtime error 26 ms 7892 KB Execution killed with signal 11
40 Runtime error 55 ms 12848 KB Execution killed with signal 11
41 Runtime error 102 ms 23008 KB Execution killed with signal 11
42 Runtime error 53 ms 12536 KB Execution killed with signal 11