Submission #673519

#	Time	Username	Problem	Language	Result	Execution time	Memory
673519		Victor	Radio (COCI22_radio)	C++17	40 / 110	1602 ms	285048 KiB

Main

#pragma GCC target ("avx,avx2,fma")
#pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;


struct Node {
    int lo,hi,val=INF;
    Node *l,*r;
    Node(int L,int R) : lo(L),hi(R) {
        if(hi-lo!=1) {
            int mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);
        }
    }

    int query(int L,int R) {
        if(hi<=L||R<=lo) return INF;
        if(L<=lo&&hi<=R) return val;
        return min(l->query(L,R),r->query(L,R));
    }

    void update(int pos,int x) {
        if(pos<lo||hi<=pos) return;
        if(hi-lo==1) {
            val=x;
            return;
        }

        l->update(pos,x);
        r->update(pos,x);
        val=min(l->val,r->val);
    }
};

const int MAXN = 1'000'000;
int n,q;
umap<int,set<int>> active_factors;
vi factors2[MAXN+1];
set<int> neighbors[MAXN+1];
bitset<MAXN+1> active;
vi primes;

void sieve() {
    bitset<1005> bs;
    for(int i=2;i<1005;++i) {
        if(bs[i]) continue;
        primes.pb(i);
        for(int j=i*i;j<1005;j+=i) bs[j]=1;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    rep(i,2,MAXN+1) if(factors2[i].empty()) for(int j=i;j<=MAXN;j+=i) factors2[j].pb(i);
    rep(i,1,MAXN+1) neighbors[i].insert(INF);
    
    sieve();
    cin>>n>>q;
    Node segtree(0,n);

    int cnt=0;
    while(q--) {
        string op;
        cin>>op;
        if(op=="S") {
            int x;
            cin>>x;
            
            int val=x;
            vi factors;
            trav(prime,primes) {
                if(prime*prime>val) break;
                if(val%prime) continue;

                while(val%prime==0) val/=prime;
                factors.pb(prime); 
            }
            if(val!=1) factors.pb(val);

            if(active[x]) {
                trav(factor,factors) {
                    active_factors[factor].erase(x);
                    auto it=active_factors[factor].lower_bound(x);
                    int lnum=-1,rnum=-1;

                    if(it!=active_factors[factor].end()) rnum=*it;
                
                    if(it!=active_factors[factor].begin()) {
                        --it;
                        lnum=*it;
                        ++it;
                    }

                    bool change=0;
                    if(lnum!=-1) {
                        if(*neighbors[lnum].begin()==x) change=1;
                        neighbors[lnum].erase(x);
                    }
                    
                    //if(rnum!=-1) neighbors[x].insert(rnum);

                    if(lnum!=-1&&rnum!=-1) {
                        neighbors[lnum].insert(rnum);
                        if(*neighbors[lnum].begin()==rnum) change=1;
                    }

                    if(change) segtree.update(lnum,*neighbors[lnum].begin());
                }

                segtree.update(x,INF);
                neighbors[x].clear();
                neighbors[x].insert(INF);

            } else {
                trav(factor,factors) {
                    active_factors[factor].insert(x);
                    auto it=active_factors[factor].find(x);
                    int lnum=-1,rnum=-1;

                    if(it!=active_factors[factor].begin()) {
                        --it;
                        lnum=*it;
                        ++it;
                    }

                    ++it;
                    if(it!=active_factors[factor].end()) rnum=*it;
                    --it;

                    bool change=0;
                    if(lnum!=-1&&rnum!=-1) {
                        if(*neighbors[lnum].begin()==rnum) change=1;
                        neighbors[lnum].erase(rnum);
                    }

                    if(lnum!=-1) {
                        neighbors[lnum].insert(x);
                        if(*neighbors[lnum].begin()==x||change) change=1;
                    }

                    if(rnum!=-1) neighbors[x].insert(rnum);

                    if(change) segtree.update(lnum,*neighbors[lnum].begin());
                }
                neighbors[x].insert(INF);
                segtree.update(x,*neighbors[x].begin());
            }

            active[x]=!active[x];

        } else {
            ++cnt;
            int lo,hi;
            cin>>lo>>hi;

            ++hi;
            /*
            if(cnt==20) {
                cout<<"active:"<<endl;
                rep(i,0,n+1) if(active[i]) cout<<i<<' ';
                cout<<endl;
                cout<<"lo = "<<lo<<" hi = "<<hi-1<<endl;
                cout<<segtree.query(lo,hi)<<endl;
            }*/
            if(segtree.query(lo,hi)<hi) cout<<"DA"<<'\n';
            else cout<<"NE"<<'\n';
        }
    }
    //cout<<endl;
    //_Exit(0);
    return 0;
}

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