oj.uz

답안 #558881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558881 2022-05-08T23:09:02 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 1000 ms 134800 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 = 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.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
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 34056 KB Output is correct
2 Correct 227 ms 51280 KB Output is correct
3 Correct 179 ms 48244 KB Output is correct
4 Correct 117 ms 31028 KB Output is correct
5 Correct 141 ms 36916 KB Output is correct
6 Correct 121 ms 33964 KB Output is correct
7 Correct 158 ms 48244 KB Output is correct
8 Correct 188 ms 52128 KB Output is correct
9 Correct 277 ms 54500 KB Output is correct
10 Correct 295 ms 55412 KB Output is correct
11 Correct 246 ms 50572 KB Output is correct
12 Correct 110 ms 30384 KB Output is correct
13 Correct 594 ms 58220 KB Output is correct
14 Correct 618 ms 58208 KB Output is correct
15 Correct 231 ms 50728 KB Output is correct
16 Correct 217 ms 51300 KB Output is correct
17 Correct 196 ms 36804 KB Output is correct
18 Correct 118 ms 30920 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 217 ms 69964 KB Execution killed with signal 11
2 Runtime error 282 ms 81912 KB Execution killed with signal 11
3 Runtime error 875 ms 130512 KB Execution killed with signal 11
4 Runtime error 288 ms 84768 KB Execution killed with signal 11
5 Runtime error 519 ms 116940 KB Execution killed with signal 11
6 Runtime error 265 ms 96212 KB Execution killed with signal 11
7 Runtime error 243 ms 69952 KB Execution killed with signal 11
8 Runtime error 237 ms 81528 KB Execution killed with signal 11
9 Runtime error 671 ms 123936 KB Execution killed with signal 11
10 Runtime error 904 ms 130332 KB Execution killed with signal 11
11 Runtime error 865 ms 124560 KB Execution killed with signal 11
12 Runtime error 433 ms 106844 KB Execution killed with signal 11
13 Runtime error 200 ms 73880 KB Execution killed with signal 11
14 Runtime error 272 ms 84824 KB Execution killed with signal 11
15 Runtime error 717 ms 122964 KB Execution killed with signal 11
16 Runtime error 302 ms 81804 KB Execution killed with signal 11
17 Runtime error 668 ms 117296 KB Execution killed with signal 11
18 Runtime error 725 ms 127644 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 746 ms 125132 KB Execution killed with signal 11
2 Runtime error 895 ms 126992 KB Execution killed with signal 11
3 Runtime error 891 ms 126788 KB Execution killed with signal 11
4 Runtime error 429 ms 108968 KB Execution killed with signal 11
5 Runtime error 344 ms 82376 KB Execution killed with signal 11
6 Runtime error 637 ms 115836 KB Execution killed with signal 11
7 Runtime error 545 ms 115876 KB Execution killed with signal 11
8 Runtime error 728 ms 125060 KB Execution killed with signal 11
9 Runtime error 792 ms 125092 KB Execution killed with signal 11
10 Runtime error 485 ms 104808 KB Execution killed with signal 11
11 Runtime error 384 ms 97440 KB Execution killed with signal 11
12 Runtime error 621 ms 114884 KB Execution killed with signal 11
13 Runtime error 843 ms 121848 KB Execution killed with signal 11
14 Runtime error 336 ms 113160 KB Execution killed with signal 11
15 Runtime error 655 ms 117708 KB Execution killed with signal 11
16 Runtime error 752 ms 118676 KB Execution killed with signal 11
17 Runtime error 663 ms 119164 KB Execution killed with signal 11
18 Runtime error 890 ms 127128 KB Execution killed with signal 11
19 Runtime error 240 ms 85220 KB Execution killed with signal 11
20 Runtime error 911 ms 126760 KB Execution killed with signal 11
21 Runtime error 426 ms 115896 KB Execution killed with signal 11
22 Runtime error 949 ms 133404 KB Execution killed with signal 11
23 Runtime error 285 ms 78616 KB Execution killed with signal 11
24 Runtime error 178 ms 69840 KB Execution killed with signal 11
25 Runtime error 508 ms 107220 KB Execution killed with signal 11
26 Runtime error 426 ms 109000 KB Execution killed with signal 11
27 Execution timed out 1033 ms 134800 KB Time limit exceeded
28 Runtime error 211 ms 80532 KB Execution killed with signal 11
29 Runtime error 718 ms 129632 KB Execution killed with signal 11
30 Runtime error 592 ms 124240 KB Execution killed with signal 11
31 Runtime error 268 ms 82952 KB Execution killed with signal 11
32 Runtime error 305 ms 89320 KB Execution killed with signal 11
33 Runtime error 181 ms 64876 KB Execution killed with signal 11
34 Runtime error 535 ms 115884 KB Execution killed with signal 11
35 Runtime error 246 ms 82040 KB Execution killed with signal 11
36 Runtime error 864 ms 131608 KB Execution killed with signal 11
37 Runtime error 344 ms 82380 KB Execution killed with signal 11
38 Runtime error 647 ms 115684 KB Execution killed with signal 11
39 Runtime error 214 ms 73452 KB Execution killed with signal 11
40 Runtime error 568 ms 113176 KB Execution killed with signal 11
41 Runtime error 595 ms 120472 KB Execution killed with signal 11
42 Runtime error 748 ms 118312 KB Execution killed with signal 11