oj.uz

Submission #1003033

# Submission time Handle Problem Language Result Execution time Memory
1003033 2024-06-20T03:12:35 Z vjudge1 Radio (COCI22_radio) C++17
110 / 110
 595 ms 148028 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 42 ms 106068 KB Output is correct
3 Correct 52 ms 106116 KB Output is correct
4 Correct 42 ms 106068 KB Output is correct
5 Correct 42 ms 106072 KB Output is correct
6 Correct 42 ms 106028 KB Output is correct
7 Correct 42 ms 106068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 118096 KB Output is correct
2 Correct 428 ms 136276 KB Output is correct
3 Correct 479 ms 142892 KB Output is correct
4 Correct 51 ms 106320 KB Output is correct
5 Correct 60 ms 107396 KB Output is correct
6 Correct 76 ms 108468 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 42 ms 106068 KB Output is correct
3 Correct 52 ms 106116 KB Output is correct
4 Correct 42 ms 106068 KB Output is correct
5 Correct 42 ms 106072 KB Output is correct
6 Correct 42 ms 106028 KB Output is correct
7 Correct 42 ms 106068 KB Output is correct
8 Correct 221 ms 118096 KB Output is correct
9 Correct 428 ms 136276 KB Output is correct
10 Correct 479 ms 142892 KB Output is correct
11 Correct 51 ms 106320 KB Output is correct
12 Correct 60 ms 107396 KB Output is correct
13 Correct 76 ms 108468 KB Output is correct
14 Correct 160 ms 107600 KB Output is correct
15 Correct 288 ms 113808 KB Output is correct
16 Correct 595 ms 148028 KB Output is correct
17 Correct 416 ms 140880 KB Output is correct
18 Correct 561 ms 144616 KB Output is correct
19 Correct 527 ms 144464 KB Output is correct
20 Correct 80 ms 108372 KB Output is correct
21 Correct 79 ms 108656 KB Output is correct
22 Correct 77 ms 108628 KB Output is correct
23 Correct 79 ms 108416 KB Output is correct