oj.uz

Submission #955292

# Submission time Handle Problem Language Result Execution time Memory
955292 2024-03-30T05:06:20 Z ezzzay Radio (COCI22_radio) C++14
110 / 110
 1038 ms 203260 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
struct segtree {
    int n;
    T e;
    T (*f)(T, T);
    vector<T> s;
    segtree(int n, T (*f)(T, T), T e):
    n(n), e(e), f(f), s(2 * n, e) {
    }
    segtree(const vector<T> &a, T (*f)(T, T), T e):
    segtree(a.size(), f, e) {
        for (int i = 2 * n - 1; i; i--) {
            s[i] = i < n ? f(s[i * 2], s[i * 2 + 1]) : a[i - n];
        }
    }
    void set(int i, const T &v) {
        for (i += n, s[i] = v; i /= 2;) {
            s[i] = f(s[i * 2], s[i * 2 + 1]);
        }
    }
    T qry(int l, int r) {
        T u(e), v(e);
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) u = f(u, s[l++]);
            if (r & 1) v = f(s[--r], v);
        }
        return f(u, v);
    }
};
int f(int a, int b) {
    return min(a, b);
}
const int I = 1e6;
vector<int> p[I + 1];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 2; i <= I; i++) {
        if (p[i].empty()) {
            for (int j = i; j <= I; j += i) {
                p[j].push_back(i);
            }
        }
    }
    int n, q;
    cin >> n >> q;
    vector<int> e(n + 1);
    segtree<int> st(n + 1, f, 1e9);
    vector<set<int>> s(n + 1), t(n + 1);
    while (q--) {
        char c;
        cin >> c;
        if (c == 'S') {
            int x;
            cin >> x;
            if (x == 1) continue;
            for (int d : p[x]) {
                if (e[x]) s[d].erase(x);
                auto it = s[d].upper_bound(x);
                int nxt = it == s[d].end() ? 1e9 : *it;
                int prv = it == s[d].begin() ? 0 : *prev(it);
                if (e[x]) {
                    if (prv) {
                        t[prv].erase(x);
                        t[prv].insert(nxt);
                        st.set(prv, *t[prv].begin());
                    }
                    t[x].clear();
                } else {
                    t[x].insert(nxt);
                    if (prv) {
                        t[prv].erase(nxt);
                        t[prv].insert(x);
                        st.set(prv, *t[prv].begin());
                    }
                }
                if (!e[x]) s[d].insert(x);
            }
            st.set(x, e[x] ? 1e9 : *t[x].begin());
            e[x] ^= 1;
        } else {
            int l, r;
            cin >> l >> r;
            cout << (st.qry(l, r + 1) <= r ? "DA" : "NE") << "\n";
        }
    }
    return 6/22;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 55720 KB Output is correct
2 Correct 278 ms 56028 KB Output is correct
3 Correct 257 ms 55724 KB Output is correct
4 Correct 255 ms 55864 KB Output is correct
5 Correct 276 ms 55832 KB Output is correct
6 Correct 259 ms 55892 KB Output is correct
7 Correct 287 ms 55844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 77652 KB Output is correct
2 Correct 819 ms 137440 KB Output is correct
3 Correct 962 ms 196512 KB Output is correct
4 Correct 305 ms 66328 KB Output is correct
5 Correct 315 ms 108588 KB Output is correct
6 Correct 391 ms 161616 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 55720 KB Output is correct
2 Correct 278 ms 56028 KB Output is correct
3 Correct 257 ms 55724 KB Output is correct
4 Correct 255 ms 55864 KB Output is correct
5 Correct 276 ms 55832 KB Output is correct
6 Correct 259 ms 55892 KB Output is correct
7 Correct 287 ms 55844 KB Output is correct
8 Correct 480 ms 77652 KB Output is correct
9 Correct 819 ms 137440 KB Output is correct
10 Correct 962 ms 196512 KB Output is correct
11 Correct 305 ms 66328 KB Output is correct
12 Correct 315 ms 108588 KB Output is correct
13 Correct 391 ms 161616 KB Output is correct
14 Correct 387 ms 57680 KB Output is correct
15 Correct 599 ms 69164 KB Output is correct
16 Correct 1038 ms 203260 KB Output is correct
17 Correct 841 ms 195752 KB Output is correct
18 Correct 937 ms 199680 KB Output is correct
19 Correct 913 ms 199672 KB Output is correct
20 Correct 374 ms 163076 KB Output is correct
21 Correct 363 ms 163152 KB Output is correct
22 Correct 359 ms 162980 KB Output is correct
23 Correct 359 ms 163152 KB Output is correct