oj.uz

Submission #1003034

# Submission time Handle Problem Language Result Execution time Memory
1003034 2024-06-20T03:13:02 Z Whisper Radio (COCI22_radio) C++17
110 / 110
 576 ms 147520 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = (n) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define N       1000000
#define MAX     1000005


int numRadio, numQuery;

bool on[MAX];
int lp[MAX];

void init(void){
    for (int i = 2; i * i <= N; ++i){
        if(lp[i]) continue;
        lp[i] = i;
        for (int j = i * i; j <= N; j += i) {
            if(!lp[j]) lp[j] = i;
        }
    }
    for (int i = 2; i <= N; ++i) if (!lp[i]) lp[i] = i;
}

int seg[MAX * 2];
void upd(int p, int val){
    for (seg[p += N] = val; p > 0; p >>= 1){
        seg[p >> 1] = min(seg[p], seg[p ^ 1]);
    }
}
int query(int l, int r){
    int ID = 1e9;
    for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1){
        if (l & 1) minimize(ID, seg[l++]);
        if (r & 1) minimize(ID, seg[--r]);
    }
    return ID;
}

set<int> st[MAX];
multiset<int> nxt[MAX];

void upd(int p){
    if ((int)nxt[p].size()) upd(p, *nxt[p].begin());
    else upd(p, 1e9);
}
void add(int x, int id){
    while (x > 1){
        int d = lp[x];
        while (x % d == 0) x /= d;

        auto it = st[d].lower_bound(id);
        assert(*it != id);

        int f = 0;
        if (it != st[d].end()){
            nxt[id].insert(*it);
            upd(id);
            f = *it;
        }

        if (it != st[d].begin()){
            it = prev(it);
            nxt[*it].insert(id);
            if (f) nxt[*it].erase(nxt[*it].find(f));
            upd(*it);
        }

        st[d].insert(id);
    }
}

void sub(int x, int id){
    while (x > 1){
        int d = lp[x];
        while (x % d == 0) x /= d;
        auto it = st[d].lower_bound(id);
        assert(*it == id);

        int f = 0;
        if (next(it) != st[d].end()){
            nxt[id].erase(nxt[id].find(*next(it)));
            f = *next(it);
            upd(id);
        }

        if (it != st[d].begin()){
            nxt[*prev(it)].erase(nxt[*prev(it)].find(id));
            if(f)
                nxt[*prev(it)].insert(f);
            upd(*prev(it));
        }
        st[d].erase(id);
    }
    assert(nxt[id].size() == 0);
}
void process(void){
    cin >> numRadio >> numQuery;
    memset(seg, 0x3f, sizeof seg);
    for (int i = 1; i <= numQuery; ++i){
        char c; cin >> c;
        if(c == 'S'){
            int x; cin >> x;
            if(on[x]) sub(x, x);
            else add(x, x);
            on[x] = !on[x];
        }
        else{
            int l, r; cin >> l >> r;
            int ID = query(l, r);
            cout << (ID <= r ? "DA\n" : "NE\n");
        }
    }
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    init();
    process();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 106068 KB Output is correct
2 Correct 41 ms 106068 KB Output is correct
3 Correct 42 ms 106064 KB Output is correct
4 Correct 40 ms 105988 KB Output is correct
5 Correct 40 ms 106068 KB Output is correct
6 Correct 39 ms 106076 KB Output is correct
7 Correct 42 ms 105976 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 117912 KB Output is correct
2 Correct 404 ms 136016 KB Output is correct
3 Correct 454 ms 142420 KB Output is correct
4 Correct 44 ms 106320 KB Output is correct
5 Correct 58 ms 107344 KB Output is correct
6 Correct 74 ms 108112 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 106068 KB Output is correct
2 Correct 41 ms 106068 KB Output is correct
3 Correct 42 ms 106064 KB Output is correct
4 Correct 40 ms 105988 KB Output is correct
5 Correct 40 ms 106068 KB Output is correct
6 Correct 39 ms 106076 KB Output is correct
7 Correct 42 ms 105976 KB Output is correct
8 Correct 217 ms 117912 KB Output is correct
9 Correct 404 ms 136016 KB Output is correct
10 Correct 454 ms 142420 KB Output is correct
11 Correct 44 ms 106320 KB Output is correct
12 Correct 58 ms 107344 KB Output is correct
13 Correct 74 ms 108112 KB Output is correct
14 Correct 161 ms 107216 KB Output is correct
15 Correct 259 ms 113024 KB Output is correct
16 Correct 576 ms 147520 KB Output is correct
17 Correct 416 ms 140052 KB Output is correct
18 Correct 489 ms 143956 KB Output is correct
19 Correct 522 ms 143696 KB Output is correct
20 Correct 74 ms 108120 KB Output is correct
21 Correct 87 ms 108012 KB Output is correct
22 Correct 85 ms 108116 KB Output is correct
23 Correct 77 ms 107980 KB Output is correct