oj.uz

Submission #563638

# Submission time Handle Problem Language Result Execution time Memory
563638 2022-05-17T19:31:06 Z fuad27 Radio (COCI22_radio) C++17
110 / 110
 1028 ms 163320 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 141028 KB Output is correct
2 Correct 407 ms 141136 KB Output is correct
3 Correct 424 ms 141004 KB Output is correct
4 Correct 437 ms 140968 KB Output is correct
5 Correct 435 ms 141004 KB Output is correct
6 Correct 434 ms 140972 KB Output is correct
7 Correct 421 ms 141008 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 147516 KB Output is correct
2 Correct 861 ms 157052 KB Output is correct
3 Correct 918 ms 160232 KB Output is correct
4 Correct 436 ms 141188 KB Output is correct
5 Correct 480 ms 141644 KB Output is correct
6 Correct 501 ms 142460 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 141028 KB Output is correct
2 Correct 407 ms 141136 KB Output is correct
3 Correct 424 ms 141004 KB Output is correct
4 Correct 437 ms 140968 KB Output is correct
5 Correct 435 ms 141004 KB Output is correct
6 Correct 434 ms 140972 KB Output is correct
7 Correct 421 ms 141008 KB Output is correct
8 Correct 720 ms 147516 KB Output is correct
9 Correct 861 ms 157052 KB Output is correct
10 Correct 918 ms 160232 KB Output is correct
11 Correct 436 ms 141188 KB Output is correct
12 Correct 480 ms 141644 KB Output is correct
13 Correct 501 ms 142460 KB Output is correct
14 Correct 568 ms 142528 KB Output is correct
15 Correct 778 ms 145684 KB Output is correct
16 Correct 1028 ms 163320 KB Output is correct
17 Correct 883 ms 159708 KB Output is correct
18 Correct 959 ms 161432 KB Output is correct
19 Correct 956 ms 161608 KB Output is correct
20 Correct 496 ms 142488 KB Output is correct
21 Correct 491 ms 142540 KB Output is correct
22 Correct 501 ms 142568 KB Output is correct
23 Correct 497 ms 142652 KB Output is correct