oj.uz

Submission #1109938

# Submission time Handle Problem Language Result Execution time Memory
1109938 2024-11-08T07:27:36 Z vjudge1 Radio (COCI22_radio) C++14
30 / 110
 897 ms 99260 KB 
#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];
set<int> S[MAXN], D;
void Div(int x) {
    D.clear();
    while (x != 1) {
        D.insert(factor[x]);
        x /= factor[x];
    }
    return ;
}
pii Get(int x, set<int> &S) {
    pii res;
    if (S.empty()) return res;
    auto it1 = S.upper_bound(x);
    if (it1 != S.end()) res.second = *it1;
    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;

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 55500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 64712 KB Output is correct
2 Correct 629 ms 82368 KB Output is correct
3 Correct 897 ms 99260 KB Output is correct
4 Correct 25 ms 58056 KB Output is correct
5 Correct 79 ms 67016 KB Output is correct
6 Correct 150 ms 81348 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 55500 KB Output isn't correct
2 Halted 0 ms 0 KB -