Submission #1003027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003027		vjudge1	Radio (COCI22_radio)	C++17	0 / 110	1581 ms	238568 KiB

Main

#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);
        }

        if (prev(it) != st[d].begin()){
            nxt[*prev(it)].erase(nxt[*prev(it)].find(id));
            nxt[*prev(it)].insert(f);
        }
        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: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 70