oj.uz

Submission #1109946

# Submission time Handle Problem Language Result Execution time Memory
1109946 2024-11-08T08:02:13 Z vjudge1 Radio (COCI22_radio) C++14
40 / 110
 1296 ms 158428 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]);
                }
            } 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 t = 0;
                        for (int v : D[b]) {
                            tie(c, d) = Get(b, S[v]);
                            if (c) t = max(t, c);
                        }
                        T.Modify(b, 1, t);
                    }
                }
                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 33 ms 79052 KB Output is correct
2 Correct 32 ms 79052 KB Output is correct
3 Correct 42 ms 79040 KB Output is correct
4 Correct 55 ms 79044 KB Output is correct
5 Correct 38 ms 79040 KB Output is correct
6 Correct 33 ms 78932 KB Output is correct
7 Correct 47 ms 79044 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 91156 KB Output is correct
2 Correct 903 ms 124856 KB Output is correct
3 Correct 1296 ms 158428 KB Output is correct
4 Correct 76 ms 85400 KB Output is correct
5 Correct 185 ms 108996 KB Output is correct
6 Correct 361 ms 139324 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 79052 KB Output is correct
2 Correct 32 ms 79052 KB Output is correct
3 Correct 42 ms 79040 KB Output is correct
4 Correct 55 ms 79044 KB Output is correct
5 Correct 38 ms 79040 KB Output is correct
6 Correct 33 ms 78932 KB Output is correct
7 Correct 47 ms 79044 KB Output is correct
8 Correct 385 ms 91156 KB Output is correct
9 Correct 903 ms 124856 KB Output is correct
10 Correct 1296 ms 158428 KB Output is correct
11 Correct 76 ms 85400 KB Output is correct
12 Correct 185 ms 108996 KB Output is correct
13 Correct 361 ms 139324 KB Output is correct
14 Incorrect 198 ms 80448 KB Output isn't correct
15 Halted 0 ms 0 KB -