oj.uz

Submission #747125

# Submission time Handle Problem Language Result Execution time Memory
747125 2023-05-23T16:20:29 Z Olympia Radio (COCI22_radio) C++17
110 / 110
 1422 ms 136272 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);
                }
            } else {
                for (int i: factors[x]) {
                    oc[i].insert(x);
                }
            }
            for (int i: factors[x]) {
                auto it = oc[i].lower_bound(x);
                if (it != oc[i].begin()) {
                    u.push_back(*(--it));
                }
            }
            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

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70736 KB Output is correct
2 Correct 37 ms 70848 KB Output is correct
3 Correct 34 ms 70764 KB Output is correct
4 Correct 35 ms 70740 KB Output is correct
5 Correct 34 ms 70664 KB Output is correct
6 Correct 33 ms 70752 KB Output is correct
7 Correct 36 ms 70656 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 81016 KB Output is correct
2 Correct 1036 ms 107916 KB Output is correct
3 Correct 1261 ms 133608 KB Output is correct
4 Correct 57 ms 75336 KB Output is correct
5 Correct 221 ms 93176 KB Output is correct
6 Correct 488 ms 115888 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70736 KB Output is correct
2 Correct 37 ms 70848 KB Output is correct
3 Correct 34 ms 70764 KB Output is correct
4 Correct 35 ms 70740 KB Output is correct
5 Correct 34 ms 70664 KB Output is correct
6 Correct 33 ms 70752 KB Output is correct
7 Correct 36 ms 70656 KB Output is correct
8 Correct 486 ms 81016 KB Output is correct
9 Correct 1036 ms 107916 KB Output is correct
10 Correct 1261 ms 133608 KB Output is correct
11 Correct 57 ms 75336 KB Output is correct
12 Correct 221 ms 93176 KB Output is correct
13 Correct 488 ms 115888 KB Output is correct
14 Correct 235 ms 70980 KB Output is correct
15 Correct 553 ms 76136 KB Output is correct
16 Correct 1416 ms 136272 KB Output is correct
17 Correct 1258 ms 132348 KB Output is correct
18 Correct 1422 ms 134248 KB Output is correct
19 Correct 1356 ms 134300 KB Output is correct
20 Correct 436 ms 115788 KB Output is correct
21 Correct 441 ms 115792 KB Output is correct
22 Correct 450 ms 115976 KB Output is correct
23 Correct 446 ms 115824 KB Output is correct