oj.uz

Submission #881040

# Submission time Handle Problem Language Result Execution time Memory
881040 2023-11-30T11:51:33 Z Cyber_Wolf Radio (COCI22_radio) C++17
40 / 110
 1500 ms 289592 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 100600 KB Output is correct
2 Correct 20 ms 100348 KB Output is correct
3 Correct 20 ms 100444 KB Output is correct
4 Correct 20 ms 100444 KB Output is correct
5 Correct 21 ms 100524 KB Output is correct
6 Correct 21 ms 100444 KB Output is correct
7 Correct 20 ms 100508 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 129860 KB Output is correct
2 Correct 1132 ms 207564 KB Output is correct
3 Correct 1349 ms 281588 KB Output is correct
4 Correct 56 ms 113036 KB Output is correct
5 Correct 326 ms 172724 KB Output is correct
6 Correct 789 ms 242652 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 100600 KB Output is correct
2 Correct 20 ms 100348 KB Output is correct
3 Correct 20 ms 100444 KB Output is correct
4 Correct 20 ms 100444 KB Output is correct
5 Correct 21 ms 100524 KB Output is correct
6 Correct 21 ms 100444 KB Output is correct
7 Correct 20 ms 100508 KB Output is correct
8 Correct 616 ms 129860 KB Output is correct
9 Correct 1132 ms 207564 KB Output is correct
10 Correct 1349 ms 281588 KB Output is correct
11 Correct 56 ms 113036 KB Output is correct
12 Correct 326 ms 172724 KB Output is correct
13 Correct 789 ms 242652 KB Output is correct
14 Correct 281 ms 102228 KB Output is correct
15 Correct 731 ms 119220 KB Output is correct
16 Execution timed out 1561 ms 289592 KB Time limit exceeded
17 Halted 0 ms 0 KB -