Submission #879978

#	Time	Username	Problem	Language	Result	Execution time	Memory
879978		HossamHero7	Radio (COCI22_radio)	C++14	110 / 110	1028 ms	109476 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e6+5;
int spf[N] , isprime[N];
set<int> primes[N];
bool on[N];
struct segTree{
    int n;
    vector<int> tree;
    bool b;
    int fun(int x,int y){
        return b ? max(x,y) : min(x,y);
    }
    segTree(int _n, bool _b){
        n = _n , b = _b;
        tree.resize(4*n+5,(b ? 0 : 1e9));
    }
    void update(int node,int l,int r,int idx,int val){
        if(l == r) return tree[node] = fun(tree[node] , val) , void();
        int md = l + r >> 1;
        idx <= md ? update(node<<1,l,md,idx,val) : update(node<<1|1,md+1,r,idx,val);
        tree[node] = fun(tree[node<<1],tree[node<<1|1]);
    }
    void set(int node,int l,int r,int idx,int val){
        if(l == r) return tree[node] = val , void();
        int md = l + r >> 1;
        idx <= md ? set(node<<1,l,md,idx,val) : set(node<<1|1,md+1,r,idx,val);
        tree[node] = fun(tree[node<<1],tree[node<<1|1]);
    }
    int query(int node,int l,int r,int lQ,int rQ){
        if(l > r || lQ > r || l > rQ) return (b ? 0 : 1e9);
        if(lQ <= l && r <= rQ) return tree[node];
        int md = l + r >> 1;
        return fun(query(node<<1,l,md,lQ,rQ) , query(node<<1|1,md+1,r,lQ,rQ));
    }
    void update(int idx,int x){
        update(1,1,n,idx,x);
    }
    void set(int idx,int x){
        set(1,1,n,idx,x);
    }
    int query(int l,int r){
        return query(1,1,n,l,r);
    }
};
vector<int> pFactors(int x){
    vector<int> tmp;
    int y = x;
    while(y != 1){
        if(tmp.empty() || tmp.back() != spf[y]) tmp.push_back(spf[y]);
        y /= spf[y];
    }
    return tmp;
}
segTree nxt(1e6,0);
segTree bef(1e6,1);
void calc(int x,bool b){
    vector<int> tmp = pFactors(x);
    for(auto p : tmp){
        if(!b) primes[p].erase(x);
        auto it = primes[p].lower_bound(x);
        if(it != primes[p].end()){
            if(b) bef.update(*it,x);
            nxt.update(x,*it);
        }
        if(it != primes[p].begin()){
            it --;
            if(b) nxt.update(*it,x);
            bef.update(x,*it);
        }
        primes[p].insert(x);
    }
}
void solve(){
    int n,q;
    cin>>n>>q;
    while(q--){
        char c;
        cin>>c;
        if(c == 'S'){
            int x;
            cin>>x;
            if(!on[x]){
                calc(x,1);
                on[x] = 1;
            }
            else {
                on[x] = 0;
                nxt.set(x,1e9);
                bef.set(x,0);
                vector<int> effected;
                vector<int> tmp = pFactors(x);
                for(auto p : tmp){
                    primes[p].erase(x);
                    auto it = primes[p].lower_bound(x);
                    if(it != primes[p].end()) effected.push_back(*it);
                    if(it != primes[p].begin()) effected.push_back(*(--it));
                }
                for(auto y : effected) nxt.set(y,1e9) , bef.set(y,0) , calc(y,0);
            }
        }
        else {
            int l,r;
            cin>>l>>r;
            int mxbef = bef.query(l,r);
            int mnnxt = nxt.query(l,r);
            cout<<(mxbef >= l || mnnxt <= r ? "DA" : "NE")<<endl;   
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    memset(isprime,1,sizeof(isprime));
    isprime[1] = 0;
    for(ll i=2;i<N;i++){
        if(!isprime[i]) continue;
        spf[i] = i;
        for(ll j=i*i;j<N;j+=i){
            if(!isprime[j]) continue;
            spf[j] = i;
            isprime[j] = 0;
        }
    }
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void segTree::update(int, int, int, int, int)':
Main.cpp:22:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'void segTree::set(int, int, int, int, int)':
Main.cpp:28:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'int segTree::query(int, int, int, int, int)':
Main.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int md = l + r >> 1;
      |                  ~~^~~

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