Submission #1231428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231428		mhn_neek	Radio (COCI22_radio)	C++20	30 / 110	651 ms	238572 KiB

Main

//In the name of God
#include<bits/stdc++.h>
/*MHN*/
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=1e6+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>>
#define set_preci(x) cout << fixed << setprecision(x);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
lli n,q;
multiset<lli> S[N];
struct Node{
	lli mn = INF,mx= -INF;
};
Node seg[N*4];
Node DEF;
Node Merge(Node a,Node b){
	Node res;
	res.mn= min(a.mn,b.mn);
	res.mx= max(a.mx,b.mx);
	return res;
}

Node Tak(lli p){
	Node res;
	if(S[p].empty()){
		res.mn = INF,res.mx = -INF;
	}
	else{
		res.mn = *S[p].begin();
		res.mx = *S[p].rbegin();
	}
	return res;
}

void build(lli l = 1,lli r = n+1,lli id = 1){
	if(r-l == 1){ 
		seg[id] = Tak(l);
		return;
	}
	lli mid = (l+r)/2;
	build(l,mid,id*2);
	build(mid,r,id*2+1);
	seg[id] = Merge(seg[id*2],seg[id*2+1]);
}

void Upd(lli l,lli r,lli p,lli id){
	if(r<=p || l>p)return;
	if(r-l == 1){
		seg[id] = Tak(p);
		return;
	}
	lli mid = (l+r)/2;
	Upd(l,mid,p,id*2);
	Upd(mid,r,p,id*2+1);
	seg[id] = Merge(seg[id*2],seg[id*2+1]);
}

Node Get(lli l,lli r,lli st,lli en,lli id){
	if(l >= en || r <= st)return DEF;
	if(l>=st && r<=en)return seg[id];
	lli mid = (l+r)/2;
	Node res = Merge(Get(l,mid,st,en,id*2) ,Get(mid,r,st,en,id*2+1) );
	return res;
}

ve v[N];
set<lli> g[N];
bool is[N];

void update(lli x){
	if(is[x]){
		for(auto i : v[x])
			g[i].erase(g[i].find(x));
	}
	lli mn = -1,mx = n+1;
	for(auto i : v[x]){
		auto it = g[i].lb(x);
		if(it != g[i].end())
			mx = min(mx,*it);
		if(it!=g[i].begin()){
			it--;
			mn = max(mn,*it);
		}
	}
	if(is[x] == 0){
		if(mn >= 0){
			S[x].insert(mn);
			S[mn].insert(x);
		}
		if(mx <= n){
			S[x].insert(mx);
			S[mx].insert(x);
		}
		for(auto i : v[x])
			g[i].insert(x);
	}
	else{
		S[x].clear();
		if(mn >= 0){
			if(S[mn].find(x)!=S[mn].end())
			S[mn].erase(S[mn].find(x));
		}
		if(mx <= n){
			if(S[mx].find(x)!=S[mx].end())
			S[mx].erase(S[mx].find(x));
		}
		
	}
	Upd(1,n+1,x,1);
	is[x] = 1 - is[x];
}



int main(){
	migmig;
	DEF.mn = INF,DEF.mx= -INF;
	for(lli i = 2; i < N; i ++){
		if(v[i].empty())
			for(lli j = i; j < N;j += i)
				v[j].PB(i);
	}
	cin>>n>>q;
	build();
	while(q--){
		char c;
		cin>>c;
		if(c == 'S'){
			lli x;
			cin>>x;
			update(x);
		}
		else{
			lli l,r;
			cin>>l>>r;
			Node nu = Get(1,n+1,l,r+1,1);
			if((nu.mn >= l && nu.mn <= r) || (nu.mx <= r && nu.mx >= l)){
				cout<<"DA"<<endl;
			}
			else{
				cout<<"NE"<<endl;
			}
		}
	}
}

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