Submission #1098534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098534		coldbr3w	Radio (COCI22_radio)	C++17	110 / 110	844 ms	211100 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 1e6 + 100;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll block = 350;
struct segment_tree_max{
    ll n;
    vector<ll>st;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            st[id] = val;
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = max(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} st;
ll n,q;
vector<ll>g[N];
bool ok[N];
ll L[N], R[N], p[N];
multiset<ll>pos[N], s[N];
void sieve(){
    for(int i = 1; i < N;i++) p[i] = i;
    for(int i = 2; i < N;i++){
        for(int j = i; j < N;j+=i) p[j] = min(p[j], i);
    }
}
void turn_on(ll i){
    ok[i] = 1;
    for(auto d : g[i]){
        auto it = pos[d].upper_bound(i);
        if(it != pos[d].begin() && it != pos[d].end()) s[*it].erase(*prev(it));
        if(it != pos[d].end()){
            ll nxt = *it;
            s[nxt].insert(i);
            st.update(nxt, nxt, (*s[nxt].rbegin()));
        }
        if(it != pos[d].begin()){
            --it; ll prv = *it;
            s[i].insert(prv);
        }
        pos[d].insert(i);
    }
    if(!s[i].size()) st.update(i, i, 0);
    else st.update(i, i, *s[i].rbegin());
}
void turn_off(ll i){
    ok[i] = 0;
    for(auto d : g[i]){
        pos[d].erase(i);
        auto it = pos[d].upper_bound(i);
        if(it != pos[d].end() && it != pos[d].begin()){
            s[*it].insert(*prev(it));
        }
        if(it != pos[d].end()){
            ll nxt = *it;
            s[nxt].erase(i);
            if(!s[nxt].size()) st.update(nxt, nxt, 0);
            else st.update(nxt, nxt, *s[nxt].rbegin());
        }
        if(it != pos[d].begin()){
            --it; ll prv = *it;
            s[i].erase(prv);
        }
    }
    if(!s[i].size()) st.update(i, i, 0);
    else st.update(i, i, *s[i].rbegin());
}
void to_thic_cau(){
    cin >> n >> q;
    for(int i = 1; i <= n;i++){
        ll x = i;
        while(x > 1){
            g[i].pb(p[x]);
            ll lst = p[x];
            while(x % lst == 0) x /= lst;
        }
    }
    st.init(n);
    while(q--){
        char ch; cin >> ch;
        if(ch == 'S'){
            ll i; cin >> i;
            if(!ok[i]) turn_on(i);
            else turn_off(i);
        }
        else{
            ll l,r; cin >> l >> r;
            if(st.get(l, r) >= l){
                cout << "DA" << '\n';
            }
            else cout << "NE" << '\n';
        }
    }
}

signed main()   
{  
    sieve();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70