제출 #799349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
799349		kebine	Radio (COCI22_radio)	C++17	110 / 110	809 ms	121180 KiB

Main

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