제출 #955289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955289		ezzzay	Radio (COCI22_radio)	C++14	30 / 110	1206 ms	201204 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ff first
#define ss second
#define pb push_back
const int N=1e6+5;

int sgt[4*N];
bool vis[N];
set<int>st[N];
vector<string>ans;
void update(int node, int L, int R, int idx, int val){
    if(L==R){
        sgt[node]=val;
        return ;
    }
    int mid=(L+R)/2;
    if(L<=idx and idx<=mid)update(node*2,L,mid,idx,val);
    else update(node*2+1,mid+1,R,idx,val);
    sgt[node]=min(sgt[node*2],sgt[node*2+1]);
}
int find(int node, int L, int R, int l, int r){
    if(l<=L and R<=r)return sgt[node];
    if(l>R or r<L)return 1e9;
    int mid=(L+R)/2;
    return min(find(node*2,L,mid,l,r),find(node*2+1,mid+1,L,l,r));
}
vector<int> primes(int n){
    vector<int>v;
    int t=sqrt(n);
    for(int i=2;i<=t;i++){
        bool u=0;
        while(n%i==0){
            n/=i;
            u=1;
        }
        if(u)v.pb(i);
    }
    if(n!=1)v.pb(n);
    return v;
}
int arr[N];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=4*n;i++)sgt[i]=1e9;
    for(int i=1;i<=n;i++){
        st[i].insert(-5);
        arr[i]=1e9;
        st[i].insert(1e9);
    }
    while(q--){
        char c;
        cin>>c;
        if(c=='S'){
            int a;
            cin>>a;
            if(a==1)continue;
            if(vis[a]){
                vis[a]=0;
                vector<int>v= primes(a);
                
                for(auto x:v){
                    
                    auto it=st[x].upper_bound(a);
                    it--; 
                    st[x].erase(st[x].find(a));
                    int h= *it;
                    if(h!=-5){
                        vector<int>vc= primes(h);
                        int c=1e9;
                        for(auto y:vc){
                            auto tmp=st[y].upper_bound(h);
                            if(*tmp!=-5){
                                c=min(c, *tmp);
                            }
                            
                        }
                    }
                    arr[h]=c;
                    update(1,1,n,h,c);
                    
                }

                arr[a]=1e9;
                update(1,1,n,a,1e9);
            }
            else{
                vis[a]=1;
                vector<int>v= primes(a);
                int c=1e9;
                for(auto x:v){
                    
                    auto it=st[x].upper_bound(a);
                    c=min(c, *it);
                    
                    it--;
                    
                    if(*it!=-5){
                        if(arr[ *it]>a){
                            update(1,1,n, *it,a);
                            arr[ *it ]=a;
                        }
                    }
                    st[x].insert(a);
                }
                arr[a]=c;
                update(1,1,n,a,c);
            }
        }
        else{
            int l,r;
            cin>>l>>r;
            if(find(1,1,n,l,r+1)<=r){
                ans.pb("DA");
            }
            else{
                ans.pb("NE");
            }
        }
    }
    for(auto a:ans)cout<<a<<endl;
}

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