oj.uz

Submission #881044

# Submission time Handle Problem Language Result Execution time Memory
881044 2023-11-30T11:58:09 Z Cyber_Wolf Radio (COCI22_radio) C++17
40 / 110
 1500 ms 233068 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();
			vector<int> up;
			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];
						up.push_back((*nxt));
					}
					if(prv != se[o[i]].begin())
					{
						prv--;
						int k = mp[*prv][o[i]];
						r[*prv][k] = r[z][i];
						up.push_back((*prv));
					}
					l[z][i] = -1e9;
					r[z][i] = 1e9;
					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);
						up.push_back((*nxt));
					}
					if(prv != se[o[i]].begin())
					{
						prv--;
						int k = mp[*prv][o[i]];
						r[*prv][k] = z;
						l[z][i] = (*prv);
						up.push_back((*prv));
					}
					se[o[i]].insert(z);
				}
			}
			up.push_back(z);
			int lst = -1;
			for(auto it : up)
			{
				if(it == lst)	continue;
				update(1, 1, n, it);
				lst = it;
			}
		}
		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:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     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 26 ms 110172 KB Output is correct
2 Correct 25 ms 110172 KB Output is correct
3 Correct 24 ms 110172 KB Output is correct
4 Correct 25 ms 110296 KB Output is correct
5 Correct 25 ms 110172 KB Output is correct
6 Correct 24 ms 110168 KB Output is correct
7 Correct 27 ms 110428 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 139344 KB Output is correct
2 Correct 1111 ms 187008 KB Output is correct
3 Correct 1299 ms 226352 KB Output is correct
4 Correct 63 ms 121444 KB Output is correct
5 Correct 332 ms 151048 KB Output is correct
6 Correct 805 ms 187476 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 110172 KB Output is correct
2 Correct 25 ms 110172 KB Output is correct
3 Correct 24 ms 110172 KB Output is correct
4 Correct 25 ms 110296 KB Output is correct
5 Correct 25 ms 110172 KB Output is correct
6 Correct 24 ms 110168 KB Output is correct
7 Correct 27 ms 110428 KB Output is correct
8 Correct 579 ms 139344 KB Output is correct
9 Correct 1111 ms 187008 KB Output is correct
10 Correct 1299 ms 226352 KB Output is correct
11 Correct 63 ms 121444 KB Output is correct
12 Correct 332 ms 151048 KB Output is correct
13 Correct 805 ms 187476 KB Output is correct
14 Correct 272 ms 110684 KB Output is correct
15 Correct 639 ms 126776 KB Output is correct
16 Execution timed out 1540 ms 233068 KB Time limit exceeded
17 Halted 0 ms 0 KB -