Submission #1162502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162502		kerem	Radio (COCI22_radio)	C++20	0 / 110	1554 ms	373572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e10
#define N 1000000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

vector<int> pdiv[N+5];
map<int,pii> mp[N+5];
set<int> s[N+5];
pii st[2*N];
int n,q,act[N+5];

void init(){
	for(int i=2;i<=n;i++){
		if(!pdiv[i].empty()) continue;
		s[i].insert(0);s[i].insert(n+1);
		for(int j=i;j<=n;j+=i){
			mp[j][i]={0,n+1};
			pdiv[j].pb(i);
		}
	}
	for(int i=1;i<2*n;i++)
		st[i]={0,n+1};
}
void update(int x){
	pii val={0,n+1};
	for(auto p:pdiv[x]){
		val.fr=max(val.fr,mp[x][p].fr);
		val.sc=min(val.sc,mp[x][p].sc);
	}
	x+=n-1;
	st[x]=val;
	x>>=1;
	while(x){
		st[x].fr=max(st[x<<1].fr,st[x<<1|1].fr);
		st[x].sc=min(st[x<<1].sc,st[x<<1|1].sc);
		x>>=1;
	}
}
pii query(int l,int r){
	l+=n-1;r+=n;
	pii ans={0,n+1};
	while(l<r){
		if(l&1){
			ans.fr=max(ans.fr,st[l++].fr);
			ans.sc=min(ans.sc,st[l++].sc);
		}
		if(r&1){
			ans.fr=max(ans.fr,st[--r].fr);
			ans.sc=min(ans.sc,st[--r].sc);
		}
		l>>=1;r>>=1;
	}
	return ans;
}
void solve(){
	cin >> n >> q;
	init();
	while(q--){
		char c;
		cin >> c;
		if(c=='S'){
			int x;
			cin >> x;
			if(act[x]){
				for(auto p:pdiv[x]){
					s[p].erase(x);
					mp[x][p]={0,n+1};
					auto it1=s[p].upper_bound(x);
					auto it2=it1--;
					//~ cout << p sp *it1 sp *it2 << endl;
					if(*it1>=1){
						mp[*it1][p].sc=*it2;
						update(*it1);
					}
					if(*it2<=n){
						mp[*it2][p].fr=*it1;
						update(*it2);
					}
				}
			}
			else{
				for(auto p:pdiv[x]){
					auto it=s[p].upper_bound(x);
					//~ cout << p sp *it << " ";
					mp[x][p].sc=*it;
					if(*it<=n){
						mp[*it][p].fr=x;
						update(*it);
					}
					it--;
					//~ cout << *it << endl;
					mp[x][p].fr=*it;
					if(*it>=1){
						mp[*it][p].sc=x;
						update(*it);
					}
					s[p].insert(x);
				}
			}
			update(x);
			act[x]^=1;
		}
		if(c=='C'){
			int l,r;
			cin >> l >> r;
			pii p=query(l,r);
			//~ cout << p.fr sp p.sc << endl;
			if(l<=p.fr || p.sc<=r) cout << "DA" << endl;
			else cout << "NE" << endl;
		}
	}
}     
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	//~ freopen("a.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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