oj.uz

Submission #955289

# Submission time Handle Problem Language Result Execution time Memory
955289 2024-03-30T04:58:07 Z ezzzay Radio (COCI22_radio) C++14
30 / 110
 1206 ms 201204 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 51548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 72176 KB Output is correct
2 Correct 938 ms 134004 KB Output is correct
3 Correct 1165 ms 201204 KB Output is correct
4 Correct 66 ms 65368 KB Output is correct
5 Correct 472 ms 118124 KB Output is correct
6 Correct 1206 ms 182892 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 51548 KB Output isn't correct
2 Halted 0 ms 0 KB -