oj.uz

Submission #566728

# Submission time Handle Problem Language Result Execution time Memory
566728 2022-05-22T18:52:19 Z dxz05 Radio (COCI22_radio) C++14
110 / 110
 1153 ms 441560 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 4e6 + 3e2;

set<int> positions[N];
int divp[N];

multiset<int> bad_segments[N];

int t[N];
int value[N];

void update(int v, int tl, int tr, int pos, int val){
    if (tl == tr){
        t[v] = val;
        return;
    }

    int tm = (tl + tr) >> 1;
    if (pos <= tm) update(v << 1, tl, tm, pos, val); else
        update(v << 1 | 1, tm + 1, tr, pos, val);

    t[v] = min(t[v << 1], t[v << 1 | 1]);
}

int get(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r) return t[v];
    if (tl > r || tr < l) return 1e9;
    int tm = (tl + tr) >> 1;
    return min(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
}

void add_segment(int l, int r){
    bad_segments[l].insert(r);
}

void del_segment(int l, int r){
    bad_segments[l].erase(bad_segments[l].find(r));
}

int n;

void update(int i){
    if (i == -1) return;

    int cur = 1e9;
    if (!bad_segments[i].empty()) cur = *bad_segments[i].begin();
    if (cur != value[i]) update(1, 1, n, i, cur);
    value[i] = cur;
}

void add_element(int p, int i){
    positions[p].insert(i);

    auto it = positions[p].find(i);
    int l = -1, r = -1;
    if (it != positions[p].begin()) l = *prev(it);
    if (next(it) != positions[p].end()) r = *next(it);

    if (l != -1) add_segment(l, i);
    if (r != -1) add_segment(i, r);
    if (l != -1 && r != -1) del_segment(l, r);

    update(i);
    update(l);
}

void del_element(int p, int i){
    auto it = positions[p].find(i);
    int l = -1, r = -1;
    if (it != positions[p].begin()) l = *prev(it);
    if (next(it) != positions[p].end()) r = *next(it);

    if (l != -1) del_segment(l, i);
    if (r != -1) del_segment(i, r);
    if (l != -1 && r != -1) add_segment(l, r);

    positions[p].erase(i);

    update(i);
    update(l);
}

bool used[N];

int main() {
    ios_base::sync_with_stdio(false);

    int q;
    cin >> n >> q;

    iota(divp + 1, divp + n + 1, 1);

    for (int i = 2; i * i <= n; i++){
        if (divp[i] != i) continue;
        for (int j = i * i; j <= n; j += i){
            divp[j] = i;
        }
    }

    fill(t, t + N, 1e9);
    fill(value, value + n + 1, 1e9);

    while (q--){
        char type;
        cin >> type;

        if (type == 'S'){
            int x;
            cin >> x;
            int i = x;

            while (x != 1){
                int p = divp[x];
                if (!used[i]) add_element(p, i); else
                    del_element(p, i);
                while (x % p == 0) x /= p;
            }

            used[i] ^= 1;
        } else {
            int l, r;
            cin >> l >> r;

            bool ok = get(1, 1, n, l, r) <= r;
            cout << (ok ? "DA\n" : "NE\n");
        }
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 391744 KB Output is correct
2 Correct 201 ms 391664 KB Output is correct
3 Correct 185 ms 391644 KB Output is correct
4 Correct 186 ms 391620 KB Output is correct
5 Correct 188 ms 391832 KB Output is correct
6 Correct 185 ms 391684 KB Output is correct
7 Correct 188 ms 391756 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 404504 KB Output is correct
2 Correct 916 ms 426084 KB Output is correct
3 Correct 998 ms 436344 KB Output is correct
4 Correct 195 ms 392720 KB Output is correct
5 Correct 215 ms 396904 KB Output is correct
6 Correct 245 ms 401880 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 391744 KB Output is correct
2 Correct 201 ms 391664 KB Output is correct
3 Correct 185 ms 391644 KB Output is correct
4 Correct 186 ms 391620 KB Output is correct
5 Correct 188 ms 391832 KB Output is correct
6 Correct 185 ms 391684 KB Output is correct
7 Correct 188 ms 391756 KB Output is correct
8 Correct 663 ms 404504 KB Output is correct
9 Correct 916 ms 426084 KB Output is correct
10 Correct 998 ms 436344 KB Output is correct
11 Correct 195 ms 392720 KB Output is correct
12 Correct 215 ms 396904 KB Output is correct
13 Correct 245 ms 401880 KB Output is correct
14 Correct 420 ms 393264 KB Output is correct
15 Correct 658 ms 399740 KB Output is correct
16 Correct 1153 ms 441560 KB Output is correct
17 Correct 1055 ms 434452 KB Output is correct
18 Correct 1114 ms 438012 KB Output is correct
19 Correct 1078 ms 438080 KB Output is correct
20 Correct 246 ms 401964 KB Output is correct
21 Correct 245 ms 401924 KB Output is correct
22 Correct 251 ms 401956 KB Output is correct
23 Correct 246 ms 402072 KB Output is correct