제출 #558893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558893		Olympia	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	17.78 / 100	630 ms	30296 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;
    int lpf[mx];
    for (int i = 0; i < mx; i++) {
        lpf[i] = -1;
    }
    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)) lpf[j] = primes[i];
            }
            if (primes.count(i)) lpf[i] = primes[i];
        }
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        if (lpf[i] == -1) {
            ans = st.query(0, M - 1) + 1;
        } else {
            vector<int> invalid;
            invalid.push_back(-1);
            int x = i;
            while (lpf[x] != -1) {
                invalid.push_back(lpf[x]);
                int a = p[lpf[x]];
                while (x % a == 0) x /= a;
            }
            sort(invalid.begin(), invalid.end());
            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: 17.77777777777778 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60