Submission #563638

#	Time	Username	Problem	Language	Result	Execution time	Memory
563638		fuad27	Radio (COCI22_radio)	C++17	110 / 110	1028 ms	163320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000'010;
const ll inf = 1e9;
vector<long long> T(2*N, inf);
vector<ll> Right(N,inf);
vector<set<ll>> p(N);
vector<vector<ll>> fact(N);
int n;
void upd(int pos) {
	ll val = Right[pos];
	for(T[pos+=n]=val;pos>1;pos>>=1) {
		T[pos>>1] = min(T[pos],T[pos^1]);
	}
}
ll que(ll l,ll r) {
	ll ans=inf;
	for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
		if(l&1)ans=min(ans,T[l++]);
		if(r&1)ans=min(ans,T[--r]);
	}
	return ans;
}

void del(int x) {
	vector<ll> wait;
	Right[x] = inf;
	upd(x);
	for(int i:fact[x]) {
		p[i].erase(x);
		auto it = p[i].upper_bound(x);
		if(it!=p[i].begin()) {
			--it;
			Right[*it]=inf;
			upd(*it);
			wait.push_back(*it);
		}
	}
	for(int i:wait) {
		for(int j:fact[i]) {
			auto it = p[j].upper_bound(i);
			if(it!=p[j].end()) {
				Right[i]=min(Right[i],*it);
			}
		}
		upd(i);
	}
}

void add(int x) {
	for(int i:fact[x]) {
		p[i].insert(x);
		auto it = p[i].upper_bound(x);
		if(it!=p[i].end()) {
			Right[x] = min(Right[x], (*it));
			upd(x);
		}
		if(it!=p[i].begin()) {
			--it;
			if(it!=p[i].begin()) {
				--it;
				Right[*it] = min(Right[*it],(ll)x);
				upd(*it);
			}
		}
	}
}

void calcprimes() {
	vector<bool> prime(N,1);
	prime[0]=prime[1]=0;
	for(int i = 2;i<N;i++) {
		if(prime[i]) {
			for(int j=i;j<N;j+=i) {
				fact[j].emplace_back(i);
				prime[j]=false;
			}
		}
	}
}

int main ()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	calcprimes();
	int q;
	cin >> n >> q;
	n++;
	char type;
	ll l,r;
	vector<bool> check(N);
	while(q--) {
		cin >> type;
		if(type == 'S') {
			cin >> l;
			if(check[l]) {
				del(l);
				check[l]=0;
			} else {
				add(l);
				check[l]=1;
			}
		} else {
			cin >> l >> r;
			// cout << que(l,r) << "\n";
			if(que(l, r) <= r) {
				cout << "DA\n";
			} else {
				cout << "NE\n";
			}
		}
	}
}

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