제출 #955292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955292		ezzzay	Radio (COCI22_radio)	C++14	110 / 110	1038 ms	203260 KiB

Main

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70