oj.uz

Submission #689457

# Submission time Handle Problem Language Result Execution time Memory
689457 2023-01-28T14:03:57 Z vjudge1 Radio (COCI22_radio) C++17
110 / 110
 1053 ms 163248 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 453 ms 140924 KB Output is correct
2 Correct 505 ms 141048 KB Output is correct
3 Correct 459 ms 141136 KB Output is correct
4 Correct 479 ms 141036 KB Output is correct
5 Correct 440 ms 141040 KB Output is correct
6 Correct 444 ms 141016 KB Output is correct
7 Correct 525 ms 141004 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 147676 KB Output is correct
2 Correct 988 ms 157156 KB Output is correct
3 Correct 981 ms 160384 KB Output is correct
4 Correct 478 ms 141092 KB Output is correct
5 Correct 569 ms 141812 KB Output is correct
6 Correct 558 ms 142564 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 140924 KB Output is correct
2 Correct 505 ms 141048 KB Output is correct
3 Correct 459 ms 141136 KB Output is correct
4 Correct 479 ms 141036 KB Output is correct
5 Correct 440 ms 141040 KB Output is correct
6 Correct 444 ms 141016 KB Output is correct
7 Correct 525 ms 141004 KB Output is correct
8 Correct 764 ms 147676 KB Output is correct
9 Correct 988 ms 157156 KB Output is correct
10 Correct 981 ms 160384 KB Output is correct
11 Correct 478 ms 141092 KB Output is correct
12 Correct 569 ms 141812 KB Output is correct
13 Correct 558 ms 142564 KB Output is correct
14 Correct 600 ms 142564 KB Output is correct
15 Correct 876 ms 145828 KB Output is correct
16 Correct 1053 ms 163248 KB Output is correct
17 Correct 927 ms 159776 KB Output is correct
18 Correct 1000 ms 161540 KB Output is correct
19 Correct 1053 ms 161608 KB Output is correct
20 Correct 501 ms 142568 KB Output is correct
21 Correct 520 ms 142540 KB Output is correct
22 Correct 484 ms 142488 KB Output is correct
23 Correct 485 ms 142504 KB Output is correct