Submission #1058336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058336		manhlinh1501	Radio (COCI22_radio)	C++17	110 / 110	348 ms	93900 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1e6 + 5;
const int oo32 = 1e9;
#define ALL(a) (a).begin(), (a).end()
int N, Q;
int prime[MAXN];
set<int> save[MAXN];
bool appear[MAXN];
int cur[MAXN];

struct segment_tree {
    int N;
    int tree[MAXN * 4];

    void init(int _N) {
        N = _N;
        for(int i = 1; i <= 4 * N; i++) tree[i] = oo32;
    }

    void update(int p, int x) {
        int id = 1, l = 1, r = N;
        while(l < r) {
            int m = (l + r) / 2;
            if(p <= m) {
                id = id * 2;
                r = m;
            } else {
                id = id * 2 + 1;
                l = m + 1;
            }
        }
        tree[id] = x;
        while(id >= 1) {
            id >>= 1;
            tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
        }
    }

    int get(int id, int l, int r, int u, int v) {
        if(r < u or l > v) return oo32;
        if(u <= l and r <= v) return tree[id];
        int m = (l + r) / 2;
        return min(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
    }

    int get(int l, int r) {
        return get(1, 1, N, l, r);
    }
} ST;

void sieve() {
    iota(prime, prime + MAXN + 1, 0);
    for(int i = 2; i * i < MAXN; i++) {
        if(prime[i] == i) {
            for(int j = i * i; j < MAXN; j += i)
                prime[j] = i;
        }
    }
}

void add(int z) {
    int x = z;
    appear[z] = true;
    while(x > 1) {
        int p = prime[x];
        save[p].emplace(z);

        auto low = save[p].lower_bound(z);
        if(low != save[p].begin()) {
            low--;
            if(cur[*low] > z) {
                ST.update(*low, z);
                cur[*low] = z;
            }
        }

        auto high = save[p].upper_bound(z);
        if(high != save[p].end()) {
            if(cur[z] > *high) {
                ST.update(z, *high);
                cur[z] = *high;
            }
        }
        while(x % p == 0) x /= p;
    }
}

void del(int x) {
    vector<int> temp;
    int tmp_x = x;
    while (tmp_x > 1) {
        int p = prime[tmp_x];

        auto it = save[p].lower_bound(x);
        if (it != save[p].begin()) {
            it--;
            if (cur[*it] == x)
                temp.push_back(*it);
        }

        while (tmp_x % p == 0)
            tmp_x /= p;
        save[p].erase(x);
    }
    cur[x] = oo32;
    ST.update(x, oo32);

    sort(ALL(temp));
    temp.resize(unique(ALL(temp)) - temp.begin());
    for (auto u : temp) {
        cur[u] = oo32;
        ST.update(u, oo32);
    }
    for (auto u : temp)
        add(u);
    appear[x] = false;
}

signed main() {
    if(fopen("code.inp", "r")) {
        freopen("code.inp", "r", stdin);
        freopen("code.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sieve();
    cin >> N >> Q;
    ST.init(N);
    for(int i = 0; i < MAXN; i++) cur[i] = oo32;

    while(Q--) {
        char type;
        cin >> type;
        if(type == 'S') {
            int x;
            cin >> x;
            if(appear[x] == false)
                add(x);
            else del(x);
        } else {
            int l, r;
            cin >> l >> r;
            int x = ST.get(l, r);
            cout << (x <= r ? "DA" : "NE") << "\n";
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen("code.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen("code.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void sieve()':
Main.cpp:54:9: warning: array subscript 1000006 is outside array bounds of 'int [1000005]' [-Warray-bounds]
   54 |     iota(prime, prime + MAXN + 1, 0);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:8:5: note: while referencing 'prime'
    8 | int prime[MAXN];
      |     ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70