oj.uz

Submission #705201

# Submission time Handle Problem Language Result Execution time Memory
705201 2023-03-03T15:01:41 Z Chal1shkan Radio (COCI22_radio) C++14
110 / 110
 1196 ms 165908 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].upper_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 426 ms 118416 KB Output is correct
2 Correct 439 ms 118436 KB Output is correct
3 Correct 428 ms 118432 KB Output is correct
4 Correct 423 ms 118648 KB Output is correct
5 Correct 444 ms 118468 KB Output is correct
6 Correct 422 ms 118520 KB Output is correct
7 Correct 459 ms 118472 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 127308 KB Output is correct
2 Correct 983 ms 146376 KB Output is correct
3 Correct 1020 ms 162124 KB Output is correct
4 Correct 455 ms 121420 KB Output is correct
5 Correct 494 ms 131708 KB Output is correct
6 Correct 524 ms 144300 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 118416 KB Output is correct
2 Correct 439 ms 118436 KB Output is correct
3 Correct 428 ms 118432 KB Output is correct
4 Correct 423 ms 118648 KB Output is correct
5 Correct 444 ms 118468 KB Output is correct
6 Correct 422 ms 118520 KB Output is correct
7 Correct 459 ms 118472 KB Output is correct
8 Correct 766 ms 127308 KB Output is correct
9 Correct 983 ms 146376 KB Output is correct
10 Correct 1020 ms 162124 KB Output is correct
11 Correct 455 ms 121420 KB Output is correct
12 Correct 494 ms 131708 KB Output is correct
13 Correct 524 ms 144300 KB Output is correct
14 Correct 656 ms 119992 KB Output is correct
15 Correct 891 ms 124724 KB Output is correct
16 Correct 1196 ms 165908 KB Output is correct
17 Correct 1091 ms 162312 KB Output is correct
18 Correct 1172 ms 164000 KB Output is correct
19 Correct 1155 ms 164028 KB Output is correct
20 Correct 607 ms 145084 KB Output is correct
21 Correct 643 ms 145184 KB Output is correct
22 Correct 604 ms 145204 KB Output is correct
23 Correct 595 ms 145176 KB Output is correct