oj.uz

Submission #705351

# Submission time Handle Problem Language Result Execution time Memory
705351 2023-03-04T06:04:01 Z Chal1shkan Radio (COCI22_radio) C++14
110 / 110
 1210 ms 165832 KB 
# 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]);
		}
		it = st[q].lower_bound(x);
		if (it != st[q].begin())
		{
			it--;
			R[*it] = min(R[*it], x);
			update(*it, R[*it]);
		}
	}
}
 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 118428 KB Output is correct
2 Correct 460 ms 118544 KB Output is correct
3 Correct 437 ms 118436 KB Output is correct
4 Correct 446 ms 118432 KB Output is correct
5 Correct 479 ms 118412 KB Output is correct
6 Correct 435 ms 118384 KB Output is correct
7 Correct 446 ms 118456 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 128116 KB Output is correct
2 Correct 1016 ms 147216 KB Output is correct
3 Correct 1093 ms 163120 KB Output is correct
4 Correct 457 ms 121536 KB Output is correct
5 Correct 489 ms 131824 KB Output is correct
6 Correct 586 ms 145196 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 118428 KB Output is correct
2 Correct 460 ms 118544 KB Output is correct
3 Correct 437 ms 118436 KB Output is correct
4 Correct 446 ms 118432 KB Output is correct
5 Correct 479 ms 118412 KB Output is correct
6 Correct 435 ms 118384 KB Output is correct
7 Correct 446 ms 118456 KB Output is correct
8 Correct 799 ms 128116 KB Output is correct
9 Correct 1016 ms 147216 KB Output is correct
10 Correct 1093 ms 163120 KB Output is correct
11 Correct 457 ms 121536 KB Output is correct
12 Correct 489 ms 131824 KB Output is correct
13 Correct 586 ms 145196 KB Output is correct
14 Correct 660 ms 119900 KB Output is correct
15 Correct 940 ms 124636 KB Output is correct
16 Correct 1210 ms 165832 KB Output is correct
17 Correct 1090 ms 162292 KB Output is correct
18 Correct 1121 ms 164024 KB Output is correct
19 Correct 1190 ms 164252 KB Output is correct
20 Correct 559 ms 145140 KB Output is correct
21 Correct 555 ms 145208 KB Output is correct
22 Correct 558 ms 145196 KB Output is correct
23 Correct 592 ms 145084 KB Output is correct