Submission #971642

#	Time	Username	Problem	Language	Result	Execution time	Memory
971642		batsukh2006	Radio (COCI22_radio)	C++17	30 / 110	790 ms	112344 KiB

Main

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
using namespace std;
 
#define MOD 1000000007
#define int long long
#define endl '\n'
const int mxN=1e6+1;
vector<bool> ok(mxN);
vector<int> tree(4*mxN,1e9),pf(mxN),mp(mxN);
int cal(int node, int L, int R, int l, int r){
    if(L>r||R<l) return 1e9;
    if(L>=l&&R<=r) return tree[node];
    return min(cal(node*2,L,(L+R)/2,l,r),cal(node*2+1,(L+R)/2+1,R,l,r));
}
void up(int node, int L, int R, int p, int v){
    if(L>p||R<p) return;
    if(L==R){
        tree[node]=v;
        return;
    }
    up(node*2,L,(L+R)/2,p,v);
    up(node*2+1,(L+R)/2+1,R,p,v);
    tree[node]=min(tree[node*2],tree[node*2+1]);
}
void solve(){
	int n,q; cin>>n>>q;
	set<int> s[n+1];
	for(int i=1; i<=n; i++) pf[i]=i;
	for(int i=2; i*i<=n; i++){
		if(!ok[i]){
			for(int k=i*i; k<=n; k+=i){
				if(!ok[k]) pf[k]=i;
				ok[k]=1;
			}
		}
	}
	while(q--){
		char c; cin>>c;
		if(c=='S'){
			int x; cin>>x;
			int real=x;
			if(!mp[x]){
				int c=cal(1,1,n,x,x);
				while(x>1){
					s[pf[x]].insert(real);
					auto it=s[pf[x]].find(real);
					int sp=1e9;
					if(it!=prev(s[pf[x]].end())) c=min(c,*next(it));
					if(it!=s[pf[x]].begin()) sp=cal(1,1,n,*prev(it),*prev(it));
					if(it!=s[pf[x]].begin()) up(1,1,n,*prev(it),min(sp,real));
					x/=pf[x];
				}
				up(1,1,n,real,c);
			}else{
				up(1,1,n,x,1e9);
				while(x>1){
					auto it=s[pf[x]].find(real);
					if(it!=s[pf[x]].begin()){
						int z=*prev(it);
						int real1=z;
						int c=1e9;
						while(z>1){
							if(pf[z]!=pf[x]){
								auto itr=s[pf[z]].find(real1);
								if(itr!=prev(s[pf[z]].end())) c=min(c,*next(itr));
							}
							z/=pf[z];
						}
						if(it!=prev(s[pf[x]].end())) up(1,1,n,real1,min(c,*next(it)));
						else up(1,1,n,real1,c);
					}
					s[pf[x]].erase(real);
					x/=pf[x];
				}
			}
			mp[real]^=1;
		}else{
			int l,r; cin>>l>>r;
			if(cal(1,1,n,l,r)<=r) cout<<"DA"<<endl;
			else cout<<"NE"<<endl;
		}
	}
}
signed main(){
    // freopen("248.in", "r", stdin);
    // freopen("248.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;	
    while(t--){
        solve();
        cout<<endl;
    }
    return 0;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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