Submission #558894

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
558894	2022-05-08T23:38:33 Z	Olympia	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	6.98413 / 100	1000 ms	94376 KB

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 = 10000000;
    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

5.55555555556 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	503 ms	88356 KB	Output isn't correct
2	Execution timed out	1100 ms	88304 KB	Time limit exceeded
3	Execution timed out	1088 ms	88276 KB	Time limit exceeded
4	Correct	553 ms	88360 KB	Output is correct
5	Correct	681 ms	88352 KB	Output is correct
6	Incorrect	461 ms	88392 KB	Output isn't correct
7	Execution timed out	1103 ms	88268 KB	Time limit exceeded
8	Execution timed out	1085 ms	88240 KB	Time limit exceeded
9	Execution timed out	1098 ms	88268 KB	Time limit exceeded
10	Execution timed out	1089 ms	88356 KB	Time limit exceeded
11	Execution timed out	1102 ms	88276 KB	Time limit exceeded
12	Correct	509 ms	88268 KB	Output is correct
13	Execution timed out	1084 ms	88404 KB	Time limit exceeded
14	Execution timed out	1096 ms	88392 KB	Time limit exceeded
15	Execution timed out	1100 ms	88324 KB	Time limit exceeded
16	Execution timed out	1101 ms	88276 KB	Time limit exceeded
17	Correct	867 ms	88360 KB	Output is correct
18	Correct	535 ms	88276 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1091 ms	89036 KB	Time limit exceeded
2	Execution timed out	1094 ms	93644 KB	Time limit exceeded
3	Execution timed out	1100 ms	92420 KB	Time limit exceeded
4	Execution timed out	1057 ms	88536 KB	Time limit exceeded
5	Execution timed out	1086 ms	91340 KB	Time limit exceeded
6	Execution timed out	1051 ms	88396 KB	Time limit exceeded
7	Execution timed out	1091 ms	88980 KB	Time limit exceeded
8	Execution timed out	1096 ms	88416 KB	Time limit exceeded
9	Execution timed out	1093 ms	92536 KB	Time limit exceeded
10	Execution timed out	1104 ms	92364 KB	Time limit exceeded
11	Execution timed out	1103 ms	90600 KB	Time limit exceeded
12	Execution timed out	1102 ms	88392 KB	Time limit exceeded
13	Execution timed out	1031 ms	88532 KB	Time limit exceeded
14	Execution timed out	1098 ms	88492 KB	Time limit exceeded
15	Execution timed out	1098 ms	90700 KB	Time limit exceeded
16	Execution timed out	1063 ms	93644 KB	Time limit exceeded
17	Execution timed out	1103 ms	88512 KB	Time limit exceeded
18	Execution timed out	1091 ms	94116 KB	Time limit exceeded

Subtask #3

1.42857142857 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1094 ms	91220 KB	Time limit exceeded
2	Execution timed out	1081 ms	91412 KB	Time limit exceeded
3	Execution timed out	1099 ms	91252 KB	Time limit exceeded
4	Execution timed out	1098 ms	88524 KB	Time limit exceeded
5	Execution timed out	1095 ms	94160 KB	Time limit exceeded
6	Execution timed out	1102 ms	88764 KB	Time limit exceeded
7	Execution timed out	1104 ms	94156 KB	Time limit exceeded
8	Execution timed out	1096 ms	91204 KB	Time limit exceeded
9	Execution timed out	1098 ms	91292 KB	Time limit exceeded
10	Execution timed out	1098 ms	88660 KB	Time limit exceeded
11	Execution timed out	1085 ms	88520 KB	Time limit exceeded
12	Execution timed out	1101 ms	88708 KB	Time limit exceeded
13	Execution timed out	1090 ms	90008 KB	Time limit exceeded
14	Execution timed out	1095 ms	88244 KB	Time limit exceeded
15	Execution timed out	1094 ms	88656 KB	Time limit exceeded
16	Execution timed out	1093 ms	88656 KB	Time limit exceeded
17	Execution timed out	1090 ms	90972 KB	Time limit exceeded
18	Execution timed out	1104 ms	91372 KB	Time limit exceeded
19	Execution timed out	1096 ms	88652 KB	Time limit exceeded
20	Execution timed out	1077 ms	91312 KB	Time limit exceeded
21	Execution timed out	1060 ms	88408 KB	Time limit exceeded
22	Execution timed out	1081 ms	94376 KB	Time limit exceeded
23	Execution timed out	1092 ms	90160 KB	Time limit exceeded
24	Execution timed out	1100 ms	88728 KB	Time limit exceeded
25	Execution timed out	1100 ms	88652 KB	Time limit exceeded
26	Execution timed out	1096 ms	88548 KB	Time limit exceeded
27	Execution timed out	1093 ms	94284 KB	Time limit exceeded
28	Execution timed out	1093 ms	88404 KB	Time limit exceeded
29	Execution timed out	1094 ms	94160 KB	Time limit exceeded
30	Execution timed out	1050 ms	92364 KB	Time limit exceeded
31	Execution timed out	1096 ms	88656 KB	Time limit exceeded
32	Execution timed out	1103 ms	88532 KB	Time limit exceeded
33	Correct	770 ms	89328 KB	Output is correct
34	Execution timed out	1102 ms	94180 KB	Time limit exceeded
35	Execution timed out	1087 ms	88372 KB	Time limit exceeded
36	Execution timed out	1052 ms	93648 KB	Time limit exceeded
37	Execution timed out	1093 ms	94144 KB	Time limit exceeded
38	Execution timed out	1076 ms	88944 KB	Time limit exceeded
39	Execution timed out	1095 ms	88492 KB	Time limit exceeded
40	Execution timed out	1087 ms	88824 KB	Time limit exceeded
41	Execution timed out	1090 ms	94244 KB	Time limit exceeded
42	Execution timed out	1095 ms	88508 KB	Time limit exceeded