oj.uz

Submission #1098534

# Submission time Handle Problem Language Result Execution time Memory
1098534 2024-10-09T13:45:37 Z coldbr3w Radio (COCI22_radio) C++17
110 / 110
 844 ms 211100 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 121936 KB Output is correct
2 Correct 71 ms 121740 KB Output is correct
3 Correct 70 ms 121684 KB Output is correct
4 Correct 71 ms 121800 KB Output is correct
5 Correct 66 ms 121728 KB Output is correct
6 Correct 72 ms 121680 KB Output is correct
7 Correct 69 ms 121692 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 138324 KB Output is correct
2 Correct 630 ms 175696 KB Output is correct
3 Correct 779 ms 206024 KB Output is correct
4 Correct 87 ms 126556 KB Output is correct
5 Correct 168 ms 146840 KB Output is correct
6 Correct 276 ms 171736 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 121936 KB Output is correct
2 Correct 71 ms 121740 KB Output is correct
3 Correct 70 ms 121684 KB Output is correct
4 Correct 71 ms 121800 KB Output is correct
5 Correct 66 ms 121728 KB Output is correct
6 Correct 72 ms 121680 KB Output is correct
7 Correct 69 ms 121692 KB Output is correct
8 Correct 353 ms 138324 KB Output is correct
9 Correct 630 ms 175696 KB Output is correct
10 Correct 779 ms 206024 KB Output is correct
11 Correct 87 ms 126556 KB Output is correct
12 Correct 168 ms 146840 KB Output is correct
13 Correct 276 ms 171736 KB Output is correct
14 Correct 227 ms 123292 KB Output is correct
15 Correct 433 ms 131620 KB Output is correct
16 Correct 825 ms 211100 KB Output is correct
17 Correct 666 ms 203972 KB Output is correct
18 Correct 733 ms 207664 KB Output is correct
19 Correct 844 ms 207440 KB Output is correct
20 Correct 271 ms 171856 KB Output is correct
21 Correct 278 ms 171884 KB Output is correct
22 Correct 284 ms 171856 KB Output is correct
23 Correct 273 ms 171820 KB Output is correct