Submission #705203

#	Time	Username	Problem	Language	Result	Execution time	Memory
705203		Chal1shkan	Radio (COCI22_radio)	C++14	110 / 110	1203 ms	164260 KiB

Main

# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 1e6 + 25;
const ll inf = 2e9 + 0;
const ll mod = 1e9 + 123;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
 
using namespace std;

ll n, q, R[maxn];
bool boo[maxn];
ll t[maxn * 4];
bool lp[maxn];
vector <ll> dl[maxn];
set <ll> st[maxn];

void precalc ()
{
	for (ll i = 2; i < maxn; ++i)
	{
		if (!lp[i])
		{
			for (ll j = i; j < maxn; j += i)
			{
				dl[j].pb(i);
				lp[j] = 1;
			}
		}
	}
}

void build (ll v = 1, ll tl = 1, ll tr = n)
{
	t[v] = inf;
	if (tl == tr)
	{
		R[tl] = inf;
		return;
	}
	ll tm = (tl + tr) >> 1;
	build (v * 2, tl, tm);
	build (v * 2 + 1, tm + 1, tr);
}

void update (ll pos, ll x, ll v = 1, ll tl = 1, ll tr = n)
{
	if (tl == tr)
	{
		t[v] = x;
		return;
	}
	ll tm = (tl + tr) >> 1;
	if (pos <= tm)
	{
		update(pos, x, v * 2, tl, tm);
	}
	else
	{
		update(pos, x, v * 2 + 1, tm + 1, tr);
	}
	t[v] = min(t[v * 2], t[v * 2 + 1]);
}

ll get (ll l, ll r, ll v = 1, ll tl = 1, ll tr = n)
{
	if (tr < l || r < tl) return inf;
	if (l <= tl && tr <= r) return t[v];
	ll tm = (tl + tr) >> 1;
	return min(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
}

void off (ll x)
{
	vector <ll> zxc;
	R[x] = inf;
	update(x, R[x]);
	for (ll q : dl[x])
	{
		st[q].erase(x);
		auto it = st[q].lower_bound(x);
		if (it != st[q].begin())
		{
			it--;
			R[*it] = inf;
			update(*it, R[*it]);
			zxc.pb(*it);
		}
	}
	for (ll w : zxc)
	{
		for (ll q : dl[w])
		{
			auto it = st[q].upper_bound(w);
			if (it != st[q].end())
			{
				R[w] = min(R[w], *it);
			}
		}
		update(w, R[w]);
	}
}

void on (ll x)
{
	for (ll q : dl[x])
	{
		st[q].insert(x);
		auto it = st[q].upper_bound(x);
		if (it != st[q].end())
		{
			R[x] = min(R[x], *it);
			update(x, R[x]);
		}
		if (it != st[q].begin())
		{
			it--;
			if(it != st[q].begin())
			{
				it--;
				R[*it] = min(R[*it], x);
				update(*it, R[*it]);
			}
		}
//		it = st[q].lower_bound(x);
//		if (it != st[q].begin())
//		{
//			it--;
//			R[*it] = min(R[*it], x);
//			update(*it, x);
//		}
	}
}

void ma1n (/* SABR */)
{
	cin >> n >> q;
	precalc ();	
	build ();
	while (q--)
	{
		char type;
		cin >> type;
		if (type == 'S')
		{
			ll x;
			cin >> x;
			if (boo[x])
			{
				off(x);
			}
			else
			{
				on(x);
			}
			boo[x] ^= 1;
		}
		if (type == 'C')
		{
			ll l, r;
			cin >> l >> r;
			if (get(l, r) <= r)
			{
				cout << "DA" << nl;
			}
			else
			{
				cout << "NE" << nl;
			}
		}
	}
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("spainting.in", "r", stdin);
//    freopen("spainting.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

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