Submission #1162592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162592		kerem	Radio (COCI22_radio)	C++20	110 / 110	857 ms	223332 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];
vector<int> pre[N+5],nxt[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/i*i+i);
		pre[i].assign(n/i+2,0);
		nxt[i].assign(n/i+2,n/i*i+i);
		for(int j=i;j<=n;j+=i)
			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,pre[p][x/p]);
		val.sc=min(val.sc,nxt[p][x/p]);
	}
	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);
			l++;
		}
		if(r&1){
			r--;
			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);
					pre[p][nxt[p][x/p]/p]=pre[p][x/p];
					nxt[p][pre[p][x/p]/p]=nxt[p][x/p];
					if(nxt[p][x/p]<=n) update(nxt[p][x/p]);
					if(pre[p][x/p]>=1) update(pre[p][x/p]);
					nxt[p][x/p]=n/p*p+p;
					pre[p][x/p]=0;
				}
			}
			else{
				for(auto p:pdiv[x]){
					auto it=s[p].upper_bound(x);
					nxt[p][x/p]=*it;
					if(*it<=n){
						pre[p][*it/p]=x;
						update(*it);
					}
					it--;
					pre[p][x/p]=*it;
					if(*it>=1){
						nxt[p][*it/p]=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);
			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: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70