oj.uz

Submission #1012775

# Submission time Handle Problem Language Result Execution time Memory
1012775 2024-07-02T15:06:53 Z TrinhKhanhDung Radio (COCI22_radio) C++14
110 / 110
 950 ms 144272 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(), v.end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(k) (1LL << (k))
#define MOD (ll)(1e9 + 7)
#define INF (ll)1e9
#define oo (ll)1e18

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 1e6 + 10;

vector<int> prime[MAX];
int cnt[MAX], k[MAX], a[MAX];
set<int> st[MAX];
int N, Q;

int Max[MAX * 4];

void update(int p, int ma){
    int i = 1, l = 1, r = N;
    while(l < r){
        int m = (l + r) >> 1;
        if(p <= m){
            i = i * 2;
            r = m;
        }
        else{
            i = i * 2 + 1;
            l = m + 1;
        }
    }
    Max[i] = ma;
    while(i > 1){
        i >>= 1;
        Max[i] = max(Max[i * 2], Max[i * 2 + 1]);
    }
}

int getVal(int i, int l, int r, int u, int v){
    if(r < u || v < l) return 0;
    if(u <= l && r <= v) return Max[i];
    int m = (l + r) >> 1;
    int L = getVal(i * 2, l, m, u, v);
    int R = getVal(i * 2 + 1, m + 1, r, u, v);
    return max(L, R);
}

int getVal(int u, int v){
    return getVal(1, 1, N, u, v);
}

void change(int x){
    int ma = 0;
    for(int k: prime[x]){
        auto it = st[k].lower_bound(x);
        if(it == st[k].begin()) continue;
        it--;
        maximize(ma, *it);
    }
    update(x, ma);
}

void solve(){
    for(int i=2; i<MAX; i++) if(cnt[i] == 0){
        for(int j=i; j<MAX; j+=i){
            cnt[j]++;
        }
    }
    for(int i=2; i<MAX; i++){
        prime[i].resize(cnt[i]);
    }
    for(int i=2; i<MAX; i++) if(k[i] == 0){
        for(int j=i; j<MAX; j+=i){
            prime[j][k[j]++] = i;
        }
    }

//    for(int i=2; i<=10; i++){
//        for(int j:prime[i]) cout << j << ' ';
//        cout << '\n';
//    }

    cin >> N >> Q;

//    {
//        while(Q--){
//            char t; cin >> t;
//            if(t == 'S'){
//                int x; cin >> x;
//                a[x] = !a[x];
//            }
//            else{
//                int l, r; cin >> l >> r;
//                bool ok = false;
//                for(int i=l; i<=r; i++) if(a[i]){
//                    for(int j=i+1; j<=r; j++) if(a[j]){
//                        if(__gcd(i, j) > 1){
//                            ok = true;
//                        }
//                    }
//                }
//                if(ok) cout << "DA\n";
//                else cout << "NE\n";
//            }
//        }
//    }

    for(int q=1; q<=Q; q++){
        char t; cin >> t;
        if(t == 'S'){
            int x; cin >> x;
            if(!a[x]){
                a[x] = true;
                for(int k: prime[x]){
                    st[k].insert(x);
                }
                change(x);
            }
            else{
                a[x] = false;
                for(int k: prime[x]){
                    st[k].erase(x);
                }
                update(x, 0);
            }
            vector<int> node;
            for(int k: prime[x]){
                auto it = st[k].upper_bound(x);
                if(it == st[k].end()) continue;
                node.push_back(*it);
            }
            cps(node);
            for(int i: node){
                change(i);
            }
        }
        else{
            int l, r;
            cin >> l >> r;

            cout << (getVal(l, r) >= l ? "DA\n" : "NE\n");
        }
        // for(int i=1; i<=N; i++) cout << getVal(i, i) << ' ';
        // cout << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
  // freopen("task.inp", "r", stdin);
  // freopen("task.out", "w", stdout);

    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 109908 KB Output is correct
2 Correct 100 ms 109828 KB Output is correct
3 Correct 104 ms 110024 KB Output is correct
4 Correct 104 ms 109908 KB Output is correct
5 Correct 102 ms 109904 KB Output is correct
6 Correct 105 ms 109908 KB Output is correct
7 Correct 103 ms 109908 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 118104 KB Output is correct
2 Correct 645 ms 132176 KB Output is correct
3 Correct 665 ms 141392 KB Output is correct
4 Correct 117 ms 111696 KB Output is correct
5 Correct 159 ms 116836 KB Output is correct
6 Correct 174 ms 123476 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 109908 KB Output is correct
2 Correct 100 ms 109828 KB Output is correct
3 Correct 104 ms 110024 KB Output is correct
4 Correct 104 ms 109908 KB Output is correct
5 Correct 102 ms 109904 KB Output is correct
6 Correct 105 ms 109908 KB Output is correct
7 Correct 103 ms 109908 KB Output is correct
8 Correct 424 ms 118104 KB Output is correct
9 Correct 645 ms 132176 KB Output is correct
10 Correct 665 ms 141392 KB Output is correct
11 Correct 117 ms 111696 KB Output is correct
12 Correct 159 ms 116836 KB Output is correct
13 Correct 174 ms 123476 KB Output is correct
14 Correct 265 ms 111444 KB Output is correct
15 Correct 524 ms 115480 KB Output is correct
16 Correct 950 ms 144272 KB Output is correct
17 Correct 688 ms 140628 KB Output is correct
18 Correct 821 ms 142480 KB Output is correct
19 Correct 852 ms 142416 KB Output is correct
20 Correct 176 ms 123468 KB Output is correct
21 Correct 195 ms 123476 KB Output is correct
22 Correct 176 ms 123512 KB Output is correct
23 Correct 184 ms 124128 KB Output is correct