oj.uz

Submission #881045

# Submission time Handle Problem Language Result Execution time Memory
881045 2023-11-30T11:59:37 Z Cyber_Wolf Radio (COCI22_radio) C++17
40 / 110
 1500 ms 229108 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];
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 < 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);
			}
			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);
			sort(up.begin(), up.end());
			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: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: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 26 ms 108380 KB Output is correct
2 Correct 24 ms 108376 KB Output is correct
3 Correct 23 ms 108380 KB Output is correct
4 Correct 24 ms 108380 KB Output is correct
5 Correct 24 ms 108380 KB Output is correct
6 Correct 24 ms 108304 KB Output is correct
7 Correct 24 ms 108380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 135360 KB Output is correct
2 Correct 1116 ms 183280 KB Output is correct
3 Correct 1274 ms 222524 KB Output is correct
4 Correct 60 ms 117332 KB Output is correct
5 Correct 324 ms 147104 KB Output is correct
6 Correct 805 ms 183380 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 108380 KB Output is correct
2 Correct 24 ms 108376 KB Output is correct
3 Correct 23 ms 108380 KB Output is correct
4 Correct 24 ms 108380 KB Output is correct
5 Correct 24 ms 108380 KB Output is correct
6 Correct 24 ms 108304 KB Output is correct
7 Correct 24 ms 108380 KB Output is correct
8 Correct 563 ms 135360 KB Output is correct
9 Correct 1116 ms 183280 KB Output is correct
10 Correct 1274 ms 222524 KB Output is correct
11 Correct 60 ms 117332 KB Output is correct
12 Correct 324 ms 147104 KB Output is correct
13 Correct 805 ms 183380 KB Output is correct
14 Correct 285 ms 109132 KB Output is correct
15 Correct 657 ms 124748 KB Output is correct
16 Execution timed out 1541 ms 229108 KB Time limit exceeded
17 Halted 0 ms 0 KB -