oj.uz

Submission #881041

# Submission time Handle Problem Language Result Execution time Memory
881041 2023-11-30T11:53:09 Z Cyber_Wolf Radio (COCI22_radio) C++17
110 / 110
 1468 ms 208412 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], seg[N << 2][2];
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 < 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]);
		}
		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);
			}
			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:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < o.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i = 0; i < o.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 100440 KB Output is correct
2 Correct 21 ms 101012 KB Output is correct
3 Correct 21 ms 100440 KB Output is correct
4 Correct 21 ms 100444 KB Output is correct
5 Correct 21 ms 100696 KB Output is correct
6 Correct 20 ms 100444 KB Output is correct
7 Correct 22 ms 100444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 120912 KB Output is correct
2 Correct 1063 ms 167252 KB Output is correct
3 Correct 1189 ms 203092 KB Output is correct
4 Correct 57 ms 106844 KB Output is correct
5 Correct 312 ms 136648 KB Output is correct
6 Correct 781 ms 168792 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 100440 KB Output is correct
2 Correct 21 ms 101012 KB Output is correct
3 Correct 21 ms 100440 KB Output is correct
4 Correct 21 ms 100444 KB Output is correct
5 Correct 21 ms 100696 KB Output is correct
6 Correct 20 ms 100444 KB Output is correct
7 Correct 22 ms 100444 KB Output is correct
8 Correct 515 ms 120912 KB Output is correct
9 Correct 1063 ms 167252 KB Output is correct
10 Correct 1189 ms 203092 KB Output is correct
11 Correct 57 ms 106844 KB Output is correct
12 Correct 312 ms 136648 KB Output is correct
13 Correct 781 ms 168792 KB Output is correct
14 Correct 272 ms 100956 KB Output is correct
15 Correct 613 ms 113544 KB Output is correct
16 Correct 1468 ms 208412 KB Output is correct
17 Correct 1206 ms 202276 KB Output is correct
18 Correct 1292 ms 206544 KB Output is correct
19 Correct 1301 ms 206360 KB Output is correct
20 Correct 785 ms 170248 KB Output is correct
21 Correct 793 ms 170532 KB Output is correct
22 Correct 790 ms 170056 KB Output is correct
23 Correct 815 ms 170172 KB Output is correct