oj.uz

Submission #705203

# Submission time Handle Problem Language Result Execution time Memory
705203 2023-03-03T15:03:33 Z Chal1shkan Radio (COCI22_radio) C++14
110 / 110
 1203 ms 164260 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]);
		}
		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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 118468 KB Output is correct
2 Correct 443 ms 118352 KB Output is correct
3 Correct 435 ms 118432 KB Output is correct
4 Correct 448 ms 118572 KB Output is correct
5 Correct 450 ms 118396 KB Output is correct
6 Correct 475 ms 118428 KB Output is correct
7 Correct 444 ms 118376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 127052 KB Output is correct
2 Correct 1018 ms 145844 KB Output is correct
3 Correct 1122 ms 161528 KB Output is correct
4 Correct 444 ms 121432 KB Output is correct
5 Correct 490 ms 131020 KB Output is correct
6 Correct 532 ms 143824 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 118468 KB Output is correct
2 Correct 443 ms 118352 KB Output is correct
3 Correct 435 ms 118432 KB Output is correct
4 Correct 448 ms 118572 KB Output is correct
5 Correct 450 ms 118396 KB Output is correct
6 Correct 475 ms 118428 KB Output is correct
7 Correct 444 ms 118376 KB Output is correct
8 Correct 745 ms 127052 KB Output is correct
9 Correct 1018 ms 145844 KB Output is correct
10 Correct 1122 ms 161528 KB Output is correct
11 Correct 444 ms 121432 KB Output is correct
12 Correct 490 ms 131020 KB Output is correct
13 Correct 532 ms 143824 KB Output is correct
14 Correct 657 ms 118772 KB Output is correct
15 Correct 930 ms 123160 KB Output is correct
16 Correct 1203 ms 164260 KB Output is correct
17 Correct 1004 ms 160276 KB Output is correct
18 Correct 1110 ms 162256 KB Output is correct
19 Correct 1137 ms 162256 KB Output is correct
20 Correct 539 ms 143664 KB Output is correct
21 Correct 531 ms 143920 KB Output is correct
22 Correct 536 ms 143820 KB Output is correct
23 Correct 539 ms 143652 KB Output is correct