oj.uz

답안 #747122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747122 2023-05-23T16:17:23 Z Olympia Radio (COCI22_radio) C++17
110 / 110
 1434 ms 138020 KB 
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <map>
#include <set>
using namespace std;
struct SegmentTreeMin {
    vector<int> vec;
    const int id = (int)1e9;
    int merge (int x, int y) {
        return min(x, y);
    }
    void update (int x, int y) {
        x += (int)vec.size()/2 - 1;
        vec[x] = y;
        while (x != 0) {
            x = (x - 1)/2;
            vec[x] = merge(vec[2 * x + 1], vec[2 * x + 2]);
        }
    }
    int query (int dum, int tl, int tr, int l, int r) {
        if (tl >= l and tr <= r) {
            return vec[dum];
        }
        if (tl > r or tr < l) {
            return id;
        }
        return merge(query(2 * dum + 1, tl, (tl + tr)/2, l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r));
    }
    int query (int l, int r) {
        return query(0, 0, (int)vec.size()/2 - 1, l, r);
    }
    void resz (int n) {
        n = (1 << ((int)log2(n) + 1));
        vec.assign(2 * n, id);
    }
};
const int MAX = (int)1e6;
//int prev[MAX + 1];
set<int> oc[MAX + 1];
bool on[MAX + 1];
SegmentTreeMin st;
vector<int> factors[MAX + 1];
void update (int x) {
    if (!on[x]) {
        st.update(x, (int)1e9);
        return;
    }
    int nxt = (int)1e9;
    for (int i: factors[x]) {
        auto it = oc[i].upper_bound(x);
        if (it != oc[i].end()) {
            nxt = min(nxt, *it);
        }
    }
    assert(nxt != x);
    st.update(x, nxt);
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        on[i] = false;
    }
    for (int i = 2; i <= N; i++) {
        if (factors[i].empty()) {
            for (int j = i; j <= N; j += i) {
                factors[j].push_back(i);
            }
        }
    }
    st.resz(N + 1);
    int prev[N + 1];
    for (int i = 0; i <= N; i++) {
        prev[i] = -1;
    }
    while (Q--) {
        char c;
        cin >> c;
        if (c == 'S') {
            int x;
            cin >> x;
            vector<int> u = {x};
            if (on[x]) {
                for (int i: factors[x]) {
                    oc[i].erase(x);
                    auto it = oc[i].lower_bound(x);
                    if (it != oc[i].begin()) {
                        u.push_back(*(--it));
                    }
                }
            } else {
                for (int i: factors[x]) {
                    auto it = oc[i].lower_bound(x);
                    if (it != oc[i].begin()) {
                        u.push_back(*(--it));
                    }
                    oc[i].insert(x);
                }
            }
            on[x] = not on[x];
            for (int i: u) {
                update(i);
            }
        } else {
            int l, r;
            cin >> l >> r;
            cout << ((st.query(l, r) <= r) ? "DA" : "NE") << '\n';
        }
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:76:9: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
   76 |     int prev[N + 1];
      |         ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 31 ms 70772 KB Output is correct
3 Correct 32 ms 70648 KB Output is correct
4 Correct 32 ms 70728 KB Output is correct
5 Correct 43 ms 70740 KB Output is correct
6 Correct 42 ms 70760 KB Output is correct
7 Correct 42 ms 70744 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 81176 KB Output is correct
2 Correct 946 ms 109212 KB Output is correct
3 Correct 1180 ms 135180 KB Output is correct
4 Correct 60 ms 75548 KB Output is correct
5 Correct 227 ms 94100 KB Output is correct
6 Correct 429 ms 117328 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 31 ms 70772 KB Output is correct
3 Correct 32 ms 70648 KB Output is correct
4 Correct 32 ms 70728 KB Output is correct
5 Correct 43 ms 70740 KB Output is correct
6 Correct 42 ms 70760 KB Output is correct
7 Correct 42 ms 70744 KB Output is correct
8 Correct 448 ms 81176 KB Output is correct
9 Correct 946 ms 109212 KB Output is correct
10 Correct 1180 ms 135180 KB Output is correct
11 Correct 60 ms 75548 KB Output is correct
12 Correct 227 ms 94100 KB Output is correct
13 Correct 429 ms 117328 KB Output is correct
14 Correct 227 ms 72364 KB Output is correct
15 Correct 654 ms 77812 KB Output is correct
16 Correct 1434 ms 138020 KB Output is correct
17 Correct 1267 ms 134504 KB Output is correct
18 Correct 1363 ms 136304 KB Output is correct
19 Correct 1293 ms 136252 KB Output is correct
20 Correct 440 ms 117388 KB Output is correct
21 Correct 458 ms 117316 KB Output is correct
22 Correct 491 ms 117396 KB Output is correct
23 Correct 453 ms 117316 KB Output is correct