Submission #881040

#	Time	Username	Problem	Language	Result	Execution time	Memory
881040		Cyber_Wolf	Radio (COCI22_radio)	C++17	40 / 110	1561 ms	289592 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lg long long 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mid (lr+hr)/2

const lg N = 1e6+5;

set<lg> se[N];
bitset<N> vis;
lg l[N][7], r[N][7], seg[N << 2][2];
map<lg, lg> mp[N];

void build(lg node, lg lr, lg hr)
{
	if(lr == hr)
	{
		seg[node][0] = 1e9;
		seg[node][1] = -1e9;
		return;
	}
	build(node << 1, lr, mid);
	build(node << 1 | 1, mid+1, hr);
	seg[node][0] = min(seg[node << 1][0], seg[node << 1 | 1][0]);
	seg[node][1] = max(seg[node << 1][1], seg[node << 1 | 1][1]);
	return;
}

void update(lg node, lg lr, lg hr, lg idx)
{
	if(lr > idx || idx > hr)	return;
	if(lr == hr)
	{
		seg[node][0] = 1e9;
		for(int i = 0; i < 7; i++)
		{
			seg[node][0] = min(seg[node][0], r[idx][i]);
		}
		seg[node][1] = -1e9;
		for(int i = 0; i < 7; i++)
		{
			seg[node][1] = max(seg[node][1], l[idx][i]);
		}
		// cout << "UPDATE\n";
		// cout << lr << ' ' << hr << '\n';
		// cout << seg[node][0] << ' ' << seg[node][1] << '\n';
		// cout << "END\n";
		return;
	}
	update(node << 1, lr, mid, idx);
	update(node << 1 | 1, mid+1, hr, idx);
	seg[node][0] = min(seg[node << 1][0], seg[node << 1 | 1][0]);
	seg[node][1] = max(seg[node << 1][1], seg[node << 1 | 1][1]);
	return ;
}

array<lg, 2> get(lg node, lg lr, lg hr, lg lq, lg hq)
{
	if(lq <= lr && hr <= hq)	return {seg[node][0], seg[node][1]};
	array<lg, 2> a = {(lg)1e9, -(lg)1e9};
	if(lr > hq || lq > hr)	return a;
	array<lg, 2> b = get(node << 1, lr, mid, lq, hq);
	a = get(node << 1 | 1, mid+1, hr, lq, hq);
	a[0] = min(a[0], b[0]);
	a[1] = max(a[1], b[1]);
	return a;
}

signed main()
{
	fastio;
	lg n, q;
	cin >> n >> q;
	for(int i = 0; i <= n; i++)	for(int j = 0; j < 7; j++)	l[i][j] = -1e9, r[i][j] = 1e9;
	build(1, 1, n);
	while(q--)
	{
		char c;
		cin >> c;
		if(c == 'S')
		{
			lg x;
			cin >> x;
			lg z = x;
			bool del = vis[x];
			if(vis[x])	vis[x] = false;
			else	vis[x] = true;
			vector<lg> o;
			for(lg i = 2; i*i <= x; i++)
			{
				while(x%i == 0)
				{
					if(o.empty() || o.back() != i)	
					{
						mp[z][i] = o.size();
						o.push_back(i);
					}
					x /= i;
				}
			}
			if(x > 1)	
			{
				mp[z][x] = o.size();
				o.push_back(x);
			}
			if(del)
			{
				for(int i = 0; i < o.size(); i++)
				{
					auto nxt = se[o[i]].upper_bound(z);
					auto prv = se[o[i]].lower_bound(z);
					if(nxt != se[o[i]].end())
					{
						lg j = mp[*nxt][o[i]];
						l[*nxt][j] = l[z][i];
						update(1, 1, n, *nxt);
					}
					if(prv != se[o[i]].begin())
					{
						prv--;
						lg k = mp[*prv][o[i]];
						r[*prv][k] = r[z][i];
						update(1, 1, n, (*prv));
					}
					l[z][i] = -1e9;
					r[z][i] = 1e9;
					update(1, 1, n, z);
					se[o[i]].erase(z);
				}
			}
			else{
				// cout << z << '\n';
				for(int i = 0; i < o.size(); i++)
				{
					auto nxt = se[o[i]].upper_bound(z);
					auto prv = se[o[i]].lower_bound(z);
					if(nxt != se[o[i]].end())
					{
						lg j = mp[*nxt][o[i]];
						l[*nxt][j] = z;
						r[z][i] = (*nxt);
						update(1, 1, n, (*nxt));
					}
					if(prv != se[o[i]].begin())
					{
						prv--;
						lg k = mp[*prv][o[i]];
						r[*prv][k] = z;
						l[z][i] = (*prv);
						update(1, 1, n, (*prv));
					}
					// cout << l[z][i] << ' ' << r[z][i] << '\n';
					update(1, 1, n, z);
					se[o[i]].insert(z);
				}
			}
		}
		else if(c == 'C')
		{
			lg l, r;
			cin >> l >> r;
			array<lg, 2> ans = get(1, 1, n, l, r);
			// cout << ans[0] << ' ' << ans[1] << '\n';
			cout << (ans[0] <= r || ans[1] >= l ? "DA\n" : "NE\n");
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i = 0; i < o.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i = 0; i < o.size(); i++)
      |                    ~~^~~~~~~~~~

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