Submission #673700

#	Time	Username	Problem	Language	Result	Execution time	Memory
673700		Victor	Radio (COCI22_radio)	C++17	110 / 110	1246 ms	200820 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;

/**
 * Author: Lucian Bicsi
 * Description: Very fast and quick segment tree.
 * Only useful for easy invariants. 0-indexed.
 * Range queries are half-open.
 */

struct SegmTree {
  vector<int> T; int n;
  SegmTree(int n) : T(2 * n, (int)2e9), n(n) {}
  
  void Update(int pos, int val) {
    for (T[pos += n] = val; pos > 1; pos /= 2)
      T[pos / 2] = min(T[pos], T[pos ^ 1]);
  }
  
  int Query(int b, int e) {
    int res = 2e9;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2) res = min(res, T[b++]);
      if (e % 2) res = min(res, T[--e]);
    }
    return res;
  }
};

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

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

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

    int cnt=0;
    while(q--) {
        string op;
        cin>>op;
        if(op=="S") {
            int x;
            cin>>x;
            if(active[x]) {
                trav(factor,factors[x]) {
                    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[x]) {
                    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());
                }
                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: 70 / 70