Submission #1319033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319033		nguyenkhangninh99	Radio (COCI22_radio)	C++20	110 / 110	702 ms	188408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5;
const int INF=1e18;
int n, q;
int spf[maxn], pid[maxn], cnt_p = 0;
multiset<int> adj[maxn], pos[maxn];
int t[4 * maxn], on[maxn];
void sieve(){
	for(int i=1;i<maxn;i++) spf[i]=i;
	for(int i=2;i*i<maxn;i++){
		if(spf[i]==i){
			for(int j=i*i;j<maxn;j+=i)
				if(spf[j]==j) spf[j]=i;
		}
	}
	for(int i=2;i<maxn;i++) if(spf[i]==i) pid[i]=++cnt_p;
}
void upd(int v,int tl,int tr,int p,int val){
	if(tl==tr) t[v]=val;
	else{
		int tm=(tl+tr)/2;
		if(p<=tm) upd(2*v,tl,tm,p,val);
		else upd(2*v+1,tm+1,tr,p,val);
		t[v]=min(t[2*v],t[2*v+1]);
	}
}
int get(int v,int tl,int tr,int l,int r){
	if(l>r) return INF;
	if(l==tl&&r==tr) return t[v];
	int tm=(tl+tr)/2;
	return min(get(2*v,tl,tm,l,min(r,tm)),get(2*v+1,tm+1,tr,max(l,tm+1),r));
}
int getmn(int u){
	if(adj[u].empty()) return INF;
	else return *adj[u].begin();
}
void add_val(int u,int v){
	adj[u].insert(v);
	upd(1, 1, n, u, getmn(u));
}
void rem_val(int u, int v){
    adj[u].erase(adj[u].find(v));
	upd(1, 1, n, u, getmn(u));
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

	sieve();
	cin >> n >> q;
	fill(t, t + 4 * maxn, INF);
	while(q--){
		char type; cin >> type;
		if(type == 'S'){
			int x; cin >> x;
			vector<int> pr;
            int tmp = x;
            while(tmp > 1){
                int p = spf[tmp];
                pr.push_back(p);
                while(tmp % p == 0) tmp /= p;
            }
			if(on[x]){
				on[x] = 0;
				for(int p:pr){
					int id=pid[p];
					auto it=pos[id].find(x);
					int L=-1,R=-1;
					if(it!=pos[id].begin()) L=*prev(it);
					if(next(it)!=pos[id].end()) R=*next(it);
					pos[id].erase(it);
					if(L!=-1){
						rem_val(L,x);
						if(R!=-1) add_val(L,R);
					}
				}
				adj[x].clear();
				upd(1,1,n,x,INF);
			}else{
				on[x]=1;
				for(int p:pr){
					int id=pid[p];
					pos[id].insert(x);
					auto it=pos[id].find(x);
					int L=-1,R=-1;
					if(it!=pos[id].begin()) L=*prev(it);
					if(next(it)!=pos[id].end()) R=*next(it);
					if(L!=-1){
						if(R!=-1) rem_val(L,R);
						add_val(L,x);
					}
					if(R!=-1) adj[x].insert(R);
				}
				upd(1,1,n,x,getmn(x));
			}
		}else{
			int l, r; cin >> l >> r;
			cout << (get(1, 1, n, l, r) <= r ? "DA" : "NE") << "\n";
		}
	}
}

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