May 2021 Lunchtime Total Components

1

I passed the subtask but not the full task. I was not going a TLE on main task but a WA. Can someone please help me understand where I went wrong?

My code:

#include <bits/stdc++.h>
using namespace std;

#define for0(i, n) for (ll i = 0; i < (int)(n); i++)
#define for1(i, n) for (ll i = 1; i <= (int)(n); i++)
#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define forr1(i, n) for (int i = (int)(n); i >= 1; --i)
#define deb(x) cout << #x << "=" << x << endl
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define tr(x) for(auto it = x.begin(); it != x.end(); it++)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define mod 1000000007
#define inf 1e17

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
typedef vector<pll> vpll;
typedef double ld;

void dk_98() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

const long long MAX_SIZE = 10000002;
vector<long long >isprime(MAX_SIZE , true);
vector<long long >prime;
vector<long long >SPF(MAX_SIZE);

void manipulated_seive(long long N)
{
    isprime[0] = isprime[1] = false ;

    for (long long int i = 2; i < N ; i++)
    {
        if (isprime[i])
        {
            prime.push_back(i);
            SPF[i] = i;
        }
        for (long long int j = 0;
                j < (int)prime.size() &&
                i * prime[j] < N && prime[j] <= SPF[i];
                j++)
        {
            isprime[i * prime[j]] = false;
            SPF[i * prime[j]] = prime[j] ;
        }
    }
}

void solve() {
    ll n; cin >> n;
    if (n <= 3) {
        cout << n - 1 << "\n";
        return;
    }
    ll j = lower_bound(prime.begin(), prime.end(), n) - prime.begin();
    if (prime[j] > n) j--;
    ll i = upper_bound(prime.begin(), prime.end(), n / 2) - prime.begin();
    //deb(prime[i]); deb(prime[j]);
    cout << j - i + 2 << "\n";
}

int main() {
    fast;
    dk_98();
    int t = 1; cin >> t;
    manipulated_seive(MAX_SIZE);
    while (t--) {
        solve();
    }
}
1 Like
3

you can optimize more. think of O(1) in the solve function and calculating the answer beforehand.

5

your logic is write but the only thing u need to learn is how lower bound and upper bound works.
first u need to check by binary search that element occurs in prime vector or not then apply lower bound and upper bound , try some test case in which n and n/2 is prime or not u will surely get your any
for simplification go through this →

#include<bits/stdc++.h>

#define ll long long int

using namespace std;

const int mod=1e9+7;

//The end result of coders personal growth is,there codes becomes there documentation

const int MAX = 10000000;

long prefix[MAX + 1];

void pre()

{

bool prime[MAX + 1];

memset(prime, true, sizeof(prime));

for (ll p = 2; p * p <= MAX; p++) 

{

    if (prime[p]) 

    {

        for (ll i = p * 2; i <= MAX; i += p)prime[i] = false;

    }

}

prefix[0] = prefix[1] = prefix[2]=0;

for (ll p = 3; p <= MAX; p++) 

{

    prefix[p] = prefix[p - 1];

    if (prime[p])prefix[p]++;

}

}

ll query(ll L, ll R)

{

return (prefix[R] - prefix[L]);

}

void solve()

{

ll N;cin>>N;

cout<< query(N/2,N) + 1 <<'\n';

}

int main(void)

{

ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);pre();

int T=1; cin>>T;

while(T–){solve();}exit(0);

}/Solved By:- Ritik Agarwal/

1 Like
6

Do you mean using something like a prefix array?

1 Like
7

But I can’t understand if that’s why it’s wrong how did it even pass on the subtask?

8

yes, the way ritik did.

9

Got it! Man I was close :sweat_smile:

10

dk_98 u need to learn that there is a difference between , range difference and upper and lower bound difference

1 Like
11

I’ll learn about that.
Thanks for the help.