제출 #558881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558881		Olympia	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	20 / 100	1033 ms	134800 KiB

brunhilda

#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 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60