oj.uz

Submission #799349

# Submission time Handle Problem Language Result Execution time Memory
799349 2023-07-31T13:10:22 Z kebine Radio (COCI22_radio) C++17
110 / 110
 809 ms 121180 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
 
const int N = 1e6 + 5;

int a[N], st[4 * N], sieve[N];
bool check[N];
priority_queue<int> pq[N];
set<int> s[N];

int merge(int x, int y) {
    return min(x, y);
}
 
void build(int x, int tl, int tr) {
    if (tl == tr) st[x] = 1e9;
    else {
        int tm = (tl + tr) / 2;
        build(2 * x, tl, tm);
        build(2 * x + 1, tm + 1, tr);
        st[x] = 1e9;
    }
}
 
void update(int x, int tl, int tr, int pos) {
    if (tl == tr) {
        while (!pq[pos].empty() and !check[-pq[pos].top()]) pq[pos].pop();
        if (pq[pos].empty() or !check[pos]) st[x] = 1e9;
        else st[x] = -pq[pos].top();
    }
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2 * x, tl, tm, pos);
        else update(2 * x + 1, tm + 1, tr, pos);
        st[x] = merge(st[2 * x], st[2 * x + 1]);
    }
}
 
int get(int x, int tl, int tr, int l, int r) {
    if (l <= tl and tr <= r) return st[x];
    if (r < tl or l > tr) return 1e9;
    int tm = (tl + tr) / 2;
    return merge(get(2 * x, tl, tm, l, r), get(2 * x + 1, tm + 1, tr, l, r));
}
 
int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    for (int i = 2; i * i <= n; i++) {
        if (sieve[i] != 0) continue;
        for (int j = i; j <= n; j += i) if (sieve[j] == 0) sieve[j] = i;
    }
    for (int i = 2; i <= n; i++) if (sieve[i] == 0) sieve[i] = i;
    build(1, 1, n);
    while (q--) {
        char c;
        cin >> c;
        if (c == 'S') {
            int x;
            cin >> x;
            if (x == 1) continue;
            if (check[x]) {
                check[x] = 0;
                update(1, 1, n, x);
                int tm = x;
                while (tm > 1) {
                    int tm2 = sieve[tm];
                    while (tm % tm2 == 0) tm /= tm2;
                    s[tm2].erase(x);
                    if (s[tm2].empty()) continue;
                    auto it = s[tm2].upper_bound(x), it2 = it;
                    if (it == s[tm2].end()) {
                        it--;
                        update(1, 1, n, *it);
                    }
                    else if (it != s[tm2].begin()) {
                        it--;
                        pq[*it].push(-*it2);
                        update(1, 1, n, *it);
                    }
                }
            }
            else {
                check[x] = 1;
                int tm = x;
                while (tm > 1) {
                    int tm2 = sieve[tm];
                    while (tm % tm2 == 0) tm /= tm2;
                    if (s[tm2].empty()) {
                        s[tm2].insert(x);
                        continue;
                    }
                    auto it = s[tm2].upper_bound(x);
                    if (it != s[tm2].begin()) {
                        it--;
                        pq[*it].push(-x);
                        update(1, 1, n, *it);
                        it++;
                    }
                    if (it != s[tm2].end()) pq[x].push(-*it);
                    s[tm2].insert(x);
                }
                update(1, 1, n, x);
            }
        }
        else {
            int l, r;
            cin >> l >> r;
            int ans = get(1, 1, n, l, r);
            if (ans > r) cout << "NE\n";
            else cout << "DA\n";
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78540 KB Output is correct
2 Correct 35 ms 78584 KB Output is correct
3 Correct 35 ms 78540 KB Output is correct
4 Correct 35 ms 78592 KB Output is correct
5 Correct 36 ms 78572 KB Output is correct
6 Correct 35 ms 78540 KB Output is correct
7 Correct 35 ms 78548 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 90188 KB Output is correct
2 Correct 546 ms 106876 KB Output is correct
3 Correct 675 ms 117268 KB Output is correct
4 Correct 45 ms 80200 KB Output is correct
5 Correct 81 ms 85940 KB Output is correct
6 Correct 131 ms 93116 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78540 KB Output is correct
2 Correct 35 ms 78584 KB Output is correct
3 Correct 35 ms 78540 KB Output is correct
4 Correct 35 ms 78592 KB Output is correct
5 Correct 36 ms 78572 KB Output is correct
6 Correct 35 ms 78540 KB Output is correct
7 Correct 35 ms 78548 KB Output is correct
8 Correct 251 ms 90188 KB Output is correct
9 Correct 546 ms 106876 KB Output is correct
10 Correct 675 ms 117268 KB Output is correct
11 Correct 45 ms 80200 KB Output is correct
12 Correct 81 ms 85940 KB Output is correct
13 Correct 131 ms 93116 KB Output is correct
14 Correct 203 ms 81784 KB Output is correct
15 Correct 322 ms 88200 KB Output is correct
16 Correct 809 ms 121180 KB Output is correct
17 Correct 599 ms 116040 KB Output is correct
18 Correct 669 ms 118604 KB Output is correct
19 Correct 662 ms 118472 KB Output is correct
20 Correct 144 ms 93184 KB Output is correct
21 Correct 143 ms 93260 KB Output is correct
22 Correct 133 ms 93256 KB Output is correct
23 Correct 137 ms 93260 KB Output is correct