oj.uz

답안 #1058339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1058339 2024-08-14T09:26:05 Z manhlinh1501 Radio (COCI22_radio) C++17
110 / 110
 323 ms 92072 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 57176 KB Output is correct
2 Correct 10 ms 57176 KB Output is correct
3 Correct 9 ms 57352 KB Output is correct
4 Correct 9 ms 57316 KB Output is correct
5 Correct 10 ms 57356 KB Output is correct
6 Correct 9 ms 57316 KB Output is correct
7 Correct 9 ms 57176 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 65108 KB Output is correct
2 Correct 236 ms 80208 KB Output is correct
3 Correct 274 ms 89680 KB Output is correct
4 Correct 13 ms 59484 KB Output is correct
5 Correct 26 ms 65740 KB Output is correct
6 Correct 49 ms 71680 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 57176 KB Output is correct
2 Correct 10 ms 57176 KB Output is correct
3 Correct 9 ms 57352 KB Output is correct
4 Correct 9 ms 57316 KB Output is correct
5 Correct 10 ms 57356 KB Output is correct
6 Correct 9 ms 57316 KB Output is correct
7 Correct 9 ms 57176 KB Output is correct
8 Correct 184 ms 65108 KB Output is correct
9 Correct 236 ms 80208 KB Output is correct
10 Correct 274 ms 89680 KB Output is correct
11 Correct 13 ms 59484 KB Output is correct
12 Correct 26 ms 65740 KB Output is correct
13 Correct 49 ms 71680 KB Output is correct
14 Correct 132 ms 57492 KB Output is correct
15 Correct 240 ms 62684 KB Output is correct
16 Correct 323 ms 92072 KB Output is correct
17 Correct 271 ms 88300 KB Output is correct
18 Correct 297 ms 90164 KB Output is correct
19 Correct 300 ms 90192 KB Output is correct
20 Correct 46 ms 71772 KB Output is correct
21 Correct 51 ms 72016 KB Output is correct
22 Correct 45 ms 71772 KB Output is correct
23 Correct 43 ms 71768 KB Output is correct