Submission #692265

#	Time	Username	Problem	Language	Result	Execution time	Memory
692265		Nelt	Radio (COCI22_radio)	C++17	0 / 110	119 ms	175412 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define sync                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll sz = 1e6 + 5;
ll prime[sz];
void precomp()
{
    for (ll i = 2; i < sz; i++)
        prime[i] = i;
    for (ll i = 2; i < sqrt(sz); i++)
        if (prime[i] == i)
            for (ll j = i * i; j < sz; j += i)
                prime[j] = i;
}
pp(ll, ll) cmp(pp(ll, ll) a, pp(ll, ll) b)
{
    return mpr(max(a.F, b.F), min(a.S, b.S));
}
struct SegTree
{
    ll n;
    vv(pp(ll, ll)) st;
    SegTree(ll Sz = 0, bool input = false)
    {
        n = Sz;
        st.resize((n + 1) << 1, mpr(-1, 1e9));
    }
    void set(ll i, pp(ll, ll) val)
    {
        st[i + n - 1] = val;
    }
    void build()
    {
        for (ll i = n - 1; i >= 1; i--)
            st[i] = cmp(st[i << 1], st[i << 1 | 1]);
    }
    void modify(ll p, pp(ll, ll) val)
    {
        for (st[p += n - 1] = val; p > 1; p >>= 1)
            st[p >> 1] = cmp(st[p], st[p ^ 1]);
    }
    pp(ll, ll) query(ll l, ll r)
    {
        pp(ll, ll) ans = mpr(-1, 1e9);
        for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = cmp(ans, st[l++]);
            if (r & 1)
                ans = cmp(ans, st[--r]);
        }
        return ans;
    }
};
SegTree st(sz);
ss(ll) s[sz];
void calc(ll x)
{
    ll v = x;
    pp(ll, ll) best = mpr(-1, 1e9);
    while (v > 1)
    {
        ll p = prime[v];
        while (v % p == 0)
            v /= p;
        if (s[p].empty())
            continue;
        if (*s[p].begin() > x)
            best = cmp(best, mpr(0, *s[p].begin()));
        elif (*s[p].rbegin() < x)
            best = cmp(best, mpr(*s[p].rbegin(), sz));
        else
            best = cmp(best, mpr(*--s[p].lower_bound(x), *s[p].upper_bound(x)));
    }
    st.modify(x, best);
}
void add(ll x)
{
    ll v = x;
    pp(ll, ll) best = mpr(-1, 1e9);
    while (v > 1)
    {
        ll p = prime[v];
        while (v % p == 0)  v /= p;
        if (s[p].empty())
            s[p].ins(x);
        elif (*s[p].begin() > x)
            best = cmp(best, mpr(0, *s[p].begin())), s[p].ins(x), calc(*s[p].begin());
        elif (*s[p].rbegin() < x)
            best = cmp(best, mpr(*s[p].rbegin(), sz)), s[p].ins(x), calc(*s[p].rbegin());
        else
            best = cmp(best, mpr(*--s[p].lower_bound(x), *s[p].upper_bound(x))), s[p].ins(x), calc(*--s[p].lower_bound(x)), calc(*s[p].upper_bound(x));
    }
}
void remove(ll x)
{
    ll v = x;
    st.modify(x, mpr(-1, 1e9));
    while (v > 1)
    {
        ll p = prime[v];
        while (v % p == 0)  v /= p;
        if (s[p].empty())
            continue;
        s[p].erase(x);
        if (*s[p].begin() > x)
            calc(*s[p].begin());
        elif (*s[p].rbegin() < x)
            calc(*s[p].rbegin());
        else
            calc(*--s[p].lower_bound(x)), calc(*s[p].upper_bound(x));
    }
}
bool query(ll l, ll r)
{
    pp(ll, ll) ans = st.query(l, r);
    return ans.F >= l or ans.S <= r;
}
void solve()
{
    ll n, q;
    cin >> n >> q;
    bool us[n + 1];
    memset(us, 0, sizeof(us));
    while (q--)
    {
        chr c;
        cin >> c;
        if (c == 'S')
        {
            ll x;
            cin >> x;
            us[x] = !us[x];
            if (!us[x])
                remove(x);
            else
                add(x);
        }
        else
        {
            ll l, r;
            cin >> l >> r;
            cout << (query(l, r) ? "DA\n" : "NE\n");
        }
    }
}
/*

*/
int main()
{
    sync
        precomp();
        ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case #" << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 70