oj.uz

Submission #1109949

# Submission time Handle Problem Language Result Execution time Memory
1109949 2024-11-08T08:09:04 Z vjudge1 Radio (COCI22_radio) C++14
110 / 110
 883 ms 161468 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];
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 82888 KB Output is correct
2 Correct 17 ms 79064 KB Output is correct
3 Correct 20 ms 79052 KB Output is correct
4 Correct 21 ms 79044 KB Output is correct
5 Correct 25 ms 79056 KB Output is correct
6 Correct 25 ms 79052 KB Output is correct
7 Correct 28 ms 79052 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 91328 KB Output is correct
2 Correct 602 ms 123588 KB Output is correct
3 Correct 703 ms 158400 KB Output is correct
4 Correct 49 ms 85444 KB Output is correct
5 Correct 186 ms 108964 KB Output is correct
6 Correct 301 ms 139380 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 82888 KB Output is correct
2 Correct 17 ms 79064 KB Output is correct
3 Correct 20 ms 79052 KB Output is correct
4 Correct 21 ms 79044 KB Output is correct
5 Correct 25 ms 79056 KB Output is correct
6 Correct 25 ms 79052 KB Output is correct
7 Correct 28 ms 79052 KB Output is correct
8 Correct 310 ms 91328 KB Output is correct
9 Correct 602 ms 123588 KB Output is correct
10 Correct 703 ms 158400 KB Output is correct
11 Correct 49 ms 85444 KB Output is correct
12 Correct 186 ms 108964 KB Output is correct
13 Correct 301 ms 139380 KB Output is correct
14 Correct 178 ms 79052 KB Output is correct
15 Correct 443 ms 86884 KB Output is correct
16 Correct 883 ms 161468 KB Output is correct
17 Correct 702 ms 159168 KB Output is correct
18 Correct 771 ms 159932 KB Output is correct
19 Correct 821 ms 159844 KB Output is correct
20 Correct 320 ms 140808 KB Output is correct
21 Correct 311 ms 140980 KB Output is correct
22 Correct 310 ms 140992 KB Output is correct
23 Correct 328 ms 140940 KB Output is correct