Submission #566728

#	Time	Username	Problem	Language	Result	Execution time	Memory
566728		dxz05	Radio (COCI22_radio)	C++14	110 / 110	1153 ms	441560 KiB

Main

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70