Submission #1291164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291164		ndan	Radio (COCI22_radio)	C++20	110 / 110	878 ms	173848 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define file "test"
#define forr(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define forf(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define rep(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define MASK(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7; // 998244353 // 1e9 + 2277 // 1e9 + 5277
const int inf = 1e18;
const int oo = 1e9 + 7;
const float eps = 1e-6;

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        }
        return 0;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        return 0;
    }
/* END OF TEMPLATE. WHAT A SIGMA! TAKE A DEEP BREATH AND READY FOR CODING :D */

int n, q, spf[maxn], st[maxn << 2];
bool on[maxn];
set<int> sett[maxn];
multiset<int> nxt[maxn];

void sieve() {
    forr(i, 2, n)
        if (!spf[i])
            for (int j = i; j <= n; j += i)
                if (!spf[j]) 
                    spf[j] = i;

}

void update(int id, int l, int r, int i, int val) {
    if (l > i || r < i) return;
    if (l == r) {
        st[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, i, val);
    update(id << 1 | 1, mid + 1, r, i, val);
    st[id] = min(st[id << 1], st[id << 1 | 1]);
}

void update(int x) {
    if (nxt[x].empty()) update(1, 1, n, x, inf);
    else update(1, 1, n, x, *nxt[x].begin());
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return inf;
    if (l >= u && r <= v) return st[id];
    int mid = (l + r) >> 1;
    int L = get(id << 1, l, mid, u, v);
    int R = get(id << 1 | 1, mid + 1, r, u, v);
    return min(L, R);
}

void add(int x, int p) {
    while (x > 1) {
        int d = spf[x];
        while (x % d == 0) x /= d;
        auto it = sett[d].lower_bound(p);
        int s = 0;
        if (it != sett[d].end()) {
            nxt[p].insert(*it);
            s = *it;
            update(p);
        }
        if (it != sett[d].begin()) {
            it--;
            nxt[*it].insert(p);
            if (s) nxt[*it].erase(nxt[*it].find(s));
            update(*it);
        }   
        sett[d].insert(p);
    }
}

void del(int x, int p) {
    while (x > 1) {
        int d = spf[x];
        while (x % d == 0) x /= d;
        auto it = sett[d].lower_bound(p);
        int s = 0;
        if (next(it) != sett[d].end()) {
            nxt[p].erase(nxt[p].find(*next(it)));
            s = *next(it);
            update(p);
        }
        if (it != sett[d].begin()) {
            it--;
            nxt[*it].erase(nxt[*it].find(p));
            if (s) nxt[*it].insert(s);
            update(*it);
        }
        sett[d].erase(p);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    sieve();
    memset(st, 63, sizeof st);
    while (q--) {
        char op;
        cin >> op;
        if (op == 'S') {
            int x;
            cin >> x;
            if (on[x]) del(x, x);
            else add(x, x);
            on[x] = !on[x];
        }
        else {
            int l, r;
            cin >> l >> r;
            int cur = get(1, 1, n, l, r);
            cout << (cur <= r ? "DA" : "NE") << "\n";
        }
    }
    return 0;
}

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