oj.uz

Submission #881043

# Submission time Handle Problem Language Result Execution time Memory
881043 2023-11-30T11:55:14 Z Cyber_Wolf Radio (COCI22_radio) C++17
40 / 110
 1500 ms 232976 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6+5;

set<int> se[N];
bitset<N> vis;
int l[N][7], r[N][7], sz[N], seg[N << 2][2];
unordered_map<int, int> mp[N];

void build(int node, int lr, int 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(int node, int lr, int hr, int idx)
{
	if(lr > idx || idx > hr)	return;
	if(lr == hr)
	{
		seg[node][0] = 1e9;
		for(int i = 0; i < sz[idx]; i++)
		{
			seg[node][0] = min(seg[node][0], r[idx][i]);
		}
		seg[node][1] = -1e9;
		for(int i = 0; i < sz[idx]; i++)
		{
			seg[node][1] = max(seg[node][1], l[idx][i]);
		}
		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<int, 2> get(int node, int lr, int hr, int lq, int hq)
{
	if(lq <= lr && hr <= hq)	return {seg[node][0], seg[node][1]};
	array<int, 2> a = {(int)1e9, -(int)1e9};
	if(lr > hq || lq > hr)	return a;
	array<int, 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;
	int 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')
		{
			int x;
			cin >> x;
			int z = x;
			bool del = vis[x];
			if(vis[x])	vis[x] = false;
			else	vis[x] = true;
			vector<int> o;
			for(int 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);
			}
			sz[z] = o.size();
			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())
					{
						int j = mp[*nxt][o[i]];
						l[*nxt][j] = l[z][i];
						update(1, 1, n, *nxt);
					}
					if(prv != se[o[i]].begin())
					{
						prv--;
						int 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())
					{
						int 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--;
						int k = mp[*prv][o[i]];
						r[*prv][k] = z;
						l[z][i] = (*prv);
						update(1, 1, n, (*prv));
					}
					update(1, 1, n, z);
					se[o[i]].insert(z);
				}
			}
		}
		else if(c == 'C')
		{
			int l, r;
			cin >> l >> r;
			array<int, 2> ans = get(1, 1, n, l, r);
			cout << (ans[0] <= r || ans[1] >= l ? "DA\n" : "NE\n");
		}
	}
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 110172 KB Output is correct
2 Correct 24 ms 110172 KB Output is correct
3 Correct 24 ms 110172 KB Output is correct
4 Correct 24 ms 110172 KB Output is correct
5 Correct 24 ms 110172 KB Output is correct
6 Correct 25 ms 110156 KB Output is correct
7 Correct 24 ms 110172 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 139348 KB Output is correct
2 Correct 1198 ms 186900 KB Output is correct
3 Correct 1329 ms 226352 KB Output is correct
4 Correct 65 ms 121340 KB Output is correct
5 Correct 331 ms 151120 KB Output is correct
6 Correct 796 ms 187388 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 110172 KB Output is correct
2 Correct 24 ms 110172 KB Output is correct
3 Correct 24 ms 110172 KB Output is correct
4 Correct 24 ms 110172 KB Output is correct
5 Correct 24 ms 110172 KB Output is correct
6 Correct 25 ms 110156 KB Output is correct
7 Correct 24 ms 110172 KB Output is correct
8 Correct 635 ms 139348 KB Output is correct
9 Correct 1198 ms 186900 KB Output is correct
10 Correct 1329 ms 226352 KB Output is correct
11 Correct 65 ms 121340 KB Output is correct
12 Correct 331 ms 151120 KB Output is correct
13 Correct 796 ms 187388 KB Output is correct
14 Correct 302 ms 110684 KB Output is correct
15 Correct 641 ms 126588 KB Output is correct
16 Execution timed out 1541 ms 232976 KB Time limit exceeded
17 Halted 0 ms 0 KB -