CNTPRIME - Counting Primes

Author: Ismail Hosen

Daffodil International University

Problem Link

//Please follow from main function

	#include<bits/stdc++.h>
	using namespace std;
	/// Typedef
	typedef long long ll;
	typedef unsigned long ul;
	typedef unsigned long long ull;
	typedef vector<int> vi;
	typedef vector<vi> vvi;
	typedef vector<ll> vll;
	typedef pair<int,int> pii;
	typedef pair<ll,ll> pll;
	typedef vector< pii > vii;
	#define pb push_back
	#define ppb pop_back
	#define MP make_pair
	#define ff first
	#define ss second
	#define sf scanf
	#define pf printf
	#define SQR(x) ((x)*(x))
	#define loop(i, y) for(int i=0; i<int(y); i++)
	#define FOR(i, x, y) for(int i=int(x); i<=int(y); i++)
	#define ROF(i, x, y) for(int i=int(x); i>=int(y); i--)
	#define ALL(c) c.begin(), c.end()
	#define SZ(c) int(c.size())
	#define CLR(x, y) memset(x, y, sizeof(x))
	#define READ(f) freopen(f, "r", stdin)
	#define WRITE(f) freopen(f, "w", stdout)
	#define FastIO ios_base::sync_with_stdio(false)
	#define tr(it, container) for(auto it = container.begin(); it != container.end(); it++)
	#define sci(x) scanf("%d", &x)
	#define scii(x, y) scanf("%d %d", &x, &y)
	#define sciii(x, y, z) scanf("%d %d %d", &x, &y, &z)
	#define scl(x) scanf("%lld", &x)
	#define scll(x, y) scanf("%lld %lld", &x, &y)
	#define sclll(x, y, z) scanf("%lld %lld %lld", &x, &y, &z)
	#define bitCheck(N,in) ((bool)(N&(1<<(in))))
	#define bitOff(N,in) (N&(~(1LL<<(in))))
	#define bitOn(N,in) (N|(1LL<<(in)))
	#define bitFlip(a,k) (a^(1LL<<(k)))
	#define unq(v) sort(all(v)), (v).erase(unique(all(v)),v.end())
	#define common(a,b) sort(all(a)), sort(all(b)), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
	#define uncommon(a,b) sort(all(a)), sort(all(b)), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())
	#define dbg(x) cout<<#x<<" = "<<x<<endl;
	const int dr[] = { 0, 1, 0, -1, -1, 1, 1, -1, -2, -2, 2, 2, -1, -1, 1, 1};
	const int dc[] = { 1, 0, -1, 0, 1, 1, -1, -1, -1, 1, -1, 1, -2, 2, -2, 2};
	#define for1(a,b) for(ll i=a; i<b; i++)
	#define rev(v) reverse(v.begin(),v.end())
	#define srt(v) sort(v.begin(),v.end())
	#define grtsrt(v) sort(v.begin(),v.end(),greater<ll>())
	/// Constants
	#define mx 20005
	#define MOD 2000005
	#define base 1000000007
	#define eps 1e-9
	#define INF 1llu<<61 // 2,305,843,009,213,693,952
	#define inf 1<<29 // 536,870,912
	#define PI acos(-1.0) // 3.1415926535897932
	ll status[MOD];
	void sieve()
	{
	ll n,i,j;
	status[1]=1;
	status[2]=0;
	for(i=4; i<MOD; i+=2)status[i] = 1;
	for(i=3; i*i<=MOD; i+=2)
	{
	if(status[i]==0)
	{
	for(j=i*i; j<MOD; j+=(i+i))
	status[j] = 1;
	}
	}
	}
	struct Tree
	{
	ll val, prop;
	} tree[mx*4];
	ll arr[mx];
	void init(ll node, ll b, ll e)
	{
	if(b==e)
	{
	tree[node].val=0;
	tree[node].prop=-1;
	return;
	}
	ll lft=node<<1;
	ll rft=lft|1;
	ll mid=(b+e)>>1;
	init(lft, b, mid);
	init(rft, mid+1, e);
	tree[node].val=tree[lft].val+tree[rft].val;
	tree[node].prop=0;
	}
	void update(ll node, ll b, ll e, ll i, ll j, ll v)
	{
	if(i>e || b>j ) return;
	if(b>=i && e<=j)
	{
	tree[node].val= (e-b+1)* !status[v];
	tree[node].prop=v;
	return;
	}
	ll lft=node<<1;
	ll rft=lft|1;
	ll mid=(b+e)>>1;
	if(tree[node].prop!=-1){
	tree[lft].val= (mid-b+1)* !status[tree[node].prop];
	tree[lft].prop= tree[node].prop;
	tree[rft].val= (e-mid) * !status[tree[node].prop];
	tree[rft].prop =tree[node].prop;
	tree[node].prop=-1;
	}
	update(lft,b,mid,i, j,v);
	update(rft,mid+1,e,i, j,v);
	tree[node].val=tree[lft].val+tree[rft].val;
	}
	ll query(ll node, ll b, ll e, ll i, ll j)
	{
	if(i>e || b>j ) return 0;
	if(b>=i && e<=j)return tree[node].val;
	ll lft=node<<1;
	ll rft=lft|1;
	ll mid=(b+e)>>1;
	if(tree[node].prop!=-1){
	tree[lft].val= (mid-b+1)* !status[tree[node].prop];
	tree[lft].prop= tree[node].prop;
	tree[rft].val= (e-mid) * !status[tree[node].prop];
	tree[rft].prop =tree[node].prop;
	tree[node].prop=-1;
	}
	ll p1=query(lft, b, mid, i, j);
	ll p2=query(rft, mid+1, e, i, j);
	return (p1+p2);
	}
	int main()
	{
	FastIO;
	#ifdef online
	clock_t tstart = clock();
	READ("input.txt");
	WRITE("output.txt");
	#endif // online
	ll t, q, k, x, n, l, r;
	sieve();
	scl(t);
	for(ll z=1; z<=t; z++)
	{
	scll(n,q);
	loop(i, n)
	{
	scl(x);
	update(1,1,n,i+1,i+1,x);
	}
	pf("Case %lld:\n", z);
	while(q--)
	{
	scl(x);
	if(x==1)
	{
	scll(l,r);
	ll ans=query(1,1,n,l,r);
	pf("\n%lld\n", ans);
	}
	else
	{
	sclll(l,r,k);
	update(1,1,n,l,r,k);
	}
	}
	}
	#ifdef online
	fprintf(stderr, "\n>>Runtime: %.10lf\n", (double)(clock()-tstart)/CLOCKS_PER_SEC);
	#endif // online
	return 0;
	}

view raw CNTPRIME - Counting Primes.cpp hosted with ❤ by GitHub