oj.uz

답안 #558863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558863 2022-05-08T19:38:43 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 1000 ms 130056 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;
                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 < (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
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 33960 KB Output is correct
2 Correct 409 ms 51432 KB Output is correct
3 Correct 261 ms 48244 KB Output is correct
4 Correct 197 ms 30996 KB Output is correct
5 Correct 235 ms 36920 KB Output is correct
6 Correct 156 ms 33964 KB Output is correct
7 Correct 267 ms 48244 KB Output is correct
8 Correct 271 ms 52220 KB Output is correct
9 Correct 366 ms 54404 KB Output is correct
10 Correct 447 ms 55280 KB Output is correct
11 Correct 354 ms 50636 KB Output is correct
12 Correct 188 ms 30392 KB Output is correct
13 Correct 891 ms 58220 KB Output is correct
14 Correct 918 ms 58228 KB Output is correct
15 Correct 322 ms 50724 KB Output is correct
16 Correct 345 ms 51432 KB Output is correct
17 Correct 308 ms 36800 KB Output is correct
18 Correct 176 ms 31020 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 344 ms 69972 KB Execution killed with signal 11
2 Runtime error 486 ms 82392 KB Execution killed with signal 11
3 Execution timed out 1060 ms 64820 KB Time limit exceeded
4 Runtime error 464 ms 84804 KB Execution killed with signal 11
5 Runtime error 854 ms 117152 KB Execution killed with signal 11
6 Runtime error 400 ms 96292 KB Execution killed with signal 11
7 Runtime error 363 ms 69976 KB Execution killed with signal 11
8 Runtime error 400 ms 81548 KB Execution killed with signal 11
9 Execution timed out 1089 ms 61660 KB Time limit exceeded
10 Execution timed out 1043 ms 64892 KB Time limit exceeded
11 Execution timed out 1089 ms 61748 KB Time limit exceeded
12 Runtime error 632 ms 106992 KB Execution killed with signal 11
13 Runtime error 362 ms 73912 KB Execution killed with signal 11
14 Runtime error 442 ms 84808 KB Execution killed with signal 11
15 Execution timed out 1085 ms 64100 KB Time limit exceeded
16 Runtime error 494 ms 82484 KB Execution killed with signal 11
17 Runtime error 996 ms 117168 KB Execution killed with signal 11
18 Execution timed out 1087 ms 106836 KB Time limit exceeded

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1050 ms 125312 KB Time limit exceeded
2 Execution timed out 1084 ms 62756 KB Time limit exceeded
3 Execution timed out 1103 ms 62628 KB Time limit exceeded
4 Runtime error 636 ms 108888 KB Execution killed with signal 11
5 Runtime error 485 ms 83032 KB Execution killed with signal 11
6 Runtime error 877 ms 115648 KB Execution killed with signal 11
7 Runtime error 754 ms 116380 KB Execution killed with signal 11
8 Execution timed out 1089 ms 69680 KB Time limit exceeded
9 Execution timed out 1099 ms 110016 KB Time limit exceeded
10 Runtime error 710 ms 104932 KB Execution killed with signal 11
11 Runtime error 635 ms 97500 KB Execution killed with signal 11
12 Runtime error 901 ms 114884 KB Execution killed with signal 11
13 Execution timed out 1092 ms 60108 KB Time limit exceeded
14 Runtime error 439 ms 113316 KB Execution killed with signal 11
15 Runtime error 963 ms 117708 KB Execution killed with signal 11
16 Execution timed out 1034 ms 118724 KB Time limit exceeded
17 Runtime error 894 ms 119412 KB Execution killed with signal 11
18 Execution timed out 1043 ms 62868 KB Time limit exceeded
19 Runtime error 391 ms 85252 KB Execution killed with signal 11
20 Execution timed out 1079 ms 62744 KB Time limit exceeded
21 Runtime error 579 ms 115856 KB Execution killed with signal 11
22 Execution timed out 1083 ms 66048 KB Time limit exceeded
23 Runtime error 371 ms 78708 KB Execution killed with signal 11
24 Runtime error 298 ms 69756 KB Execution killed with signal 11
25 Runtime error 655 ms 107324 KB Execution killed with signal 11
26 Runtime error 607 ms 109012 KB Execution killed with signal 11
27 Execution timed out 1099 ms 66792 KB Time limit exceeded
28 Runtime error 308 ms 80532 KB Execution killed with signal 11
29 Execution timed out 1036 ms 130056 KB Time limit exceeded
30 Runtime error 809 ms 125260 KB Execution killed with signal 11
31 Runtime error 369 ms 83100 KB Execution killed with signal 11
32 Runtime error 385 ms 89336 KB Execution killed with signal 11
33 Runtime error 225 ms 64988 KB Execution killed with signal 11
34 Runtime error 708 ms 116344 KB Execution killed with signal 11
35 Runtime error 327 ms 82164 KB Execution killed with signal 11
36 Execution timed out 1095 ms 65308 KB Time limit exceeded
37 Runtime error 441 ms 82872 KB Execution killed with signal 11
38 Runtime error 811 ms 115776 KB Execution killed with signal 11
39 Runtime error 315 ms 73528 KB Execution killed with signal 11
40 Runtime error 736 ms 113360 KB Execution killed with signal 11
41 Runtime error 741 ms 120932 KB Execution killed with signal 11
42 Runtime error 895 ms 118448 KB Execution killed with signal 11