oj.uz

Submission #1003581

# Submission time Handle Problem Language Result Execution time Memory
1003581 2024-06-20T13:20:23 Z ulianamalanyak Radio (COCI22_radio) C++14
10 / 110
 1500 ms 383772 KB 
#include "bits/stdc++.h"
 
using namespace std;
 
#define endl '\n'
#define INF 1000000000000
 
typedef int ll;
 
const int DIM=1e6+7;
 
ll n,q,multiple;
set<ll> tmm[4*DIM];
int ts[4*DIM];
int a[DIM];
set<ll> prime,s,factors[DIM];
bool fl;
 
ll gcd(ll p1, ll p2)
{
	for (auto x:prime)
	{
		if (p1%x==0&&p2%x==0) return x;
	}
	return 1;
}
 
void euclid()
{
	for (int i=2;i<=1000000;i++)
	{
		if (a[i]==0)
		{
			prime.insert(i);
 
			for (int j=i;j<=1000000;j+=i)
			{
				a[j]=1;
			}
		}
	}

	for (int i=2;i<=1000000;i++)
	{
		if (prime.count(i)) factors[i].insert(i);
		else 
		{
			ll res=0;
			for (auto x:prime)
			{
				if (i%x==0)
				{
					res=x;
					break;
				}
			}

			for (auto x:factors[i/res])
			{
				factors[i].insert(x);
			}
			factors[i].insert(res);
		}
	}
}
 
void init(ll v, ll tl, ll tr)
{
	if (tl==tr)
	{
		ts[v]=0;
		return;
	}
 
	ll mid=(tl+tr)/2;
	init(2*v+1,tl,mid);
	init(2*v+2,mid+1,tr);
	ts[v]=0;
}
 
void status(ll v, ll tl, ll tr, ll u)
{
	if (u<tl||u>tr) return;
 
	if (tl==tr)
	{
		if (tmm[v].size()>0) tmm[v].clear();
		else 
		{
			for (auto x:factors[u])
			{
				tmm[v].insert(x);
			}
		}
		return;
	}
 
	ll mid=(tl+tr)/2;
	status(2*v+1,tl,mid,u);
	status(2*v+2,mid+1,tr,u);
 
	ts[v]=max(ts[2*v+1],ts[2*v+2]);
 
	tmm[v].clear();
	for (auto x:tmm[2*v+1])
	{
		if (tmm[2*v+2].count(x)) ts[v]=1;
		tmm[v].insert(x);
	}
 
	for (auto x:tmm[2*v+2])
	{
		tmm[v].insert(x);
	}
}
 
void query(ll v, ll tl, ll tr, ll l, ll r)
{
	if (r<tl||l>tr) return;
 
	if (l<=tl&&tr<=r) 
	{
		if (ts[v]) fl=1;
		for (auto x:tmm[v])
		{
			if (s.count(x)) fl=1;
			s.insert(x);
		}
		return;
	}
	
	ll mid=(tl+tr)/2;
	query(2*v+1,tl,mid,l,r);
	query(2*v+2,mid+1,tr,l,r);
	return;
}
 
int main()
{
    //freopen ("input.txt","r",stdin);
    //freopen ("output.txt","w",stdout);
    
    cin >> n >> q;
 
	euclid();
 
	init(0,1,n);
 
	while(q--)
	{
		char c;
 
		cin >> c;
 
		if (c=='S')
		{
			ll x;
			cin >> x;
			status(0,1,n,x);
		}
		else 
		{
			ll l,r;
			cin >> l >> r;
			s.clear();
			fl=0;
			query(0,1,n,l,r);
 
			if (fl) cout << "DA" << endl;
			else cout << "NE" << endl;
		}
	}
  
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 376656 KB Output is correct
2 Correct 366 ms 376660 KB Output is correct
3 Correct 370 ms 376720 KB Output is correct
4 Correct 357 ms 376912 KB Output is correct
5 Correct 386 ms 376656 KB Output is correct
6 Correct 343 ms 376824 KB Output is correct
7 Correct 364 ms 376644 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1530 ms 383772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 376656 KB Output is correct
2 Correct 366 ms 376660 KB Output is correct
3 Correct 370 ms 376720 KB Output is correct
4 Correct 357 ms 376912 KB Output is correct
5 Correct 386 ms 376656 KB Output is correct
6 Correct 343 ms 376824 KB Output is correct
7 Correct 364 ms 376644 KB Output is correct
8 Execution timed out 1530 ms 383772 KB Time limit exceeded
9 Halted 0 ms 0 KB -