Submission #540214

#	Time	Username	Problem	Language	Result	Execution time	Memory
540214		eecs	Radio (COCI22_radio)	C++17	110 / 110	1433 ms	212444 KiB

Main

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

const int maxn = 1000010;
int n, q, cur[maxn], val[maxn], mn[maxn << 2];
vector<int> d[maxn];
set<int> S[maxn];
multiset<int> E[maxn];

#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
void upd(int k, int l, int r, int p) {
    if (l == r) { mn[k] = val[l]; return; }
    mid >= p ? upd(ls, l, mid, p) : upd(rs, mid + 1, r, p);
    mn[k] = min(mn[ls], mn[rs]);
}

int query(int k, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return mn[k];
    int s = INT_MAX;
    if (mid >= ql) s = query(ls, l, mid, ql, qr);
    if (mid < qr) s = min(s, query(rs, mid + 1, r, ql, qr));
    return s;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 2; i <= n; i++) if (d[i].empty()) {
        for (int j = i; j <= n; j += i) d[j].push_back(i);
    }
    memset(mn, 0x3f, sizeof(mn));
    auto upd = [&](int p) {
        if (!p) return;
        val[p] = E[p].empty() ? INT_MAX : *E[p].begin();
        ::upd(1, 1, n, p);
    };
    while (q--) {
        char op;
        int x, y;
        cin >> op >> x;
        if (op == 'S') {
            for (int p : d[x]) {
                if (!cur[x]) {
                    auto it = S[p].insert(x).first;
                    int l = it == S[p].begin() ? 0 : *prev(it);
                    int r = next(it) == S[p].end() ? 0 : *next(it);
                    if (l) E[l].insert(x);
                    if (r) E[x].insert(r);
                    if (l && r) E[l].erase(E[l].find(r));
                    upd(l), upd(x);
                } else {
                    auto it = S[p].lower_bound(x);
                    int l = it == S[p].begin() ? 0 : *prev(it);
                    int r = next(it) == S[p].end() ? 0 : *next(it);
                    if (l) E[l].erase(E[l].find(x));
                    if (r) E[x].erase(E[x].find(r));
                    if (l && r) E[l].insert(r);
                    upd(l), upd(x);
                    S[p].erase(x);
                }
            }
            cur[x] ^= 1;
        } else {
            cin >> y;
            cout << (query(1, 1, n, x, y) <= y ? "DA\n" : "NE\n");
        }
    }
    return 0;
}

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