oj.uz

Submission #1098651

# Submission time Handle Problem Language Result Execution time Memory
1098651 2024-10-09T16:21:26 Z flyingkite Radio (COCI22_radio) C++17
110 / 110
 1121 ms 211116 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 64 ms 121764 KB Output is correct
2 Correct 73 ms 121792 KB Output is correct
3 Correct 77 ms 121756 KB Output is correct
4 Correct 59 ms 121680 KB Output is correct
5 Correct 59 ms 121688 KB Output is correct
6 Correct 58 ms 121688 KB Output is correct
7 Correct 76 ms 121664 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 138412 KB Output is correct
2 Correct 861 ms 175700 KB Output is correct
3 Correct 930 ms 205936 KB Output is correct
4 Correct 77 ms 126544 KB Output is correct
5 Correct 157 ms 146800 KB Output is correct
6 Correct 277 ms 171856 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 121764 KB Output is correct
2 Correct 73 ms 121792 KB Output is correct
3 Correct 77 ms 121756 KB Output is correct
4 Correct 59 ms 121680 KB Output is correct
5 Correct 59 ms 121688 KB Output is correct
6 Correct 58 ms 121688 KB Output is correct
7 Correct 76 ms 121664 KB Output is correct
8 Correct 461 ms 138412 KB Output is correct
9 Correct 861 ms 175700 KB Output is correct
10 Correct 930 ms 205936 KB Output is correct
11 Correct 77 ms 126544 KB Output is correct
12 Correct 157 ms 146800 KB Output is correct
13 Correct 277 ms 171856 KB Output is correct
14 Correct 244 ms 123404 KB Output is correct
15 Correct 646 ms 131668 KB Output is correct
16 Correct 1121 ms 211116 KB Output is correct
17 Correct 812 ms 203784 KB Output is correct
18 Correct 942 ms 207676 KB Output is correct
19 Correct 865 ms 207428 KB Output is correct
20 Correct 269 ms 171920 KB Output is correct
21 Correct 317 ms 171900 KB Output is correct
22 Correct 284 ms 171860 KB Output is correct
23 Correct 293 ms 171744 KB Output is correct