Submission #1109949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109949		vjudge1	Radio (COCI22_radio)	C++14	110 / 110	883 ms	161468 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int MAXN = 1e6 + 505;

int n, m;

vector<int> Prime;
bool notprime[MAXN];
int factor[MAXN];
void Euler() {
    factor[1] = 1, notprime[1] = 1;
    for (int i = 2; i < MAXN; ++i) {
        if (!notprime[i]) {
            Prime.push_back(i);
            factor[i] = i;
        }
        for (int j : Prime) {
            if (i * j >= MAXN) break;
            notprime[i * j] = 1, factor[i * j] = j;
            if (i % j == 0) break;
        }
    }
    return ;
}

bool vis[MAXN];
vector<int> D[MAXN];
set<int> S[MAXN];
pii Get(int x, set<int> &S) {
    pii res;
    if (S.empty()) return res;
    auto it = S.upper_bound(x);
    if (it != S.end()) res.second = *it;
    if (x > *S.begin()) res.first = *--S.lower_bound(x);
    return res;
}

struct SGT {
    int l[MAXN << 2], r[MAXN << 2], a[MAXN << 2];
#define lc(r1) (r1 << 1)
#define rc(r1) (r1 << 1 | 1)
#define mid ((l[pos] + r[pos]) >> 1)
    inline void UP(int pos) {a[pos] = max(a[lc(pos)], a[rc(pos)]);}
    void Build(int L, int R, int pos) {
        l[pos] = L, r[pos] = R;
        if (L == R) return ;
        return Build(L, mid, lc(pos)), Build(mid + 1, R, rc(pos));
    }
    void Modify(int q, int pos, int k) {
        if (l[pos] == r[pos]) return a[pos] = k, void();
        Modify(q, q <= mid ? lc(pos) : rc(pos), k);
        return UP(pos);
    }
    int Query(int q, int w, int pos) {
        if (q <= l[pos] && w >= r[pos]) return a[pos];
        if (q >  mid) return Query(q, w, rc(pos));
        if (w <= mid) return Query(q, w, lc(pos));
        return max(Query(q, w, lc(pos)), Query(q, w, rc(pos)));
    }
#undef mid
} T;

int main() {
    Euler();
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

    for (int i = 1, cur; i <= n; ++i) {
        cur = i;
        while (cur != 1) {
            D[i].push_back(factor[cur]);
            cur /= factor[cur];
        }
        sort(D[i].begin(), D[i].end());
        D[i].erase(unique(D[i].begin(), D[i].end()), D[i].end());
    }

    T.Build(1, n, 1);
    char op;
    int x, y, a, b, c, d;
    while (m--) {
        cin >> op >> x;
        if (op == 'S') {
            if (vis[x]) {
                T.Modify(x, 1, 0);
                for (int v : D[x]) {
                    S[v].erase(x);
                    tie(a, b) = Get(x, S[v]);
                    if (b) {
                        int t = 0;
                        for (int u : D[b]) {
                            tie(c, d) = Get(b, S[u]);
                            if (c) t = max(t, c);
                        }
                        T.Modify(b, 1, t);
                    }
                }
            } else {
                int pre = 0;
                for (int v : D[x]) {
                    tie(a, b) = Get(x, S[v]);
                    S[v].insert(x);
                    pre = max(pre, a);
                    if (b) {
                        int tmp = T.Query(b, b, 1);
                        if (x > tmp) T.Modify(b, 1, x);
                    }
                }
                T.Modify(x, 1, pre);
            }
            vis[x] ^= 1;
        } else {
            cin >> y;
            cout << (T.Query(x, y, 1) >= x ? "DA" : "NE") << '\n';
        }
    }

    return 0;
}

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