My code Tle's for this problem but I am sure about the complexity. Here's my code --
#include "bits/stdc++.h"
using namespace std;
#define lli long long
#define gc getchar_unlocked
#define MAX 10000001
bool vv[MAX];
int len, sp[MAX];
int dp[MAX];
map<int, map<lli,lli> > dpsum;
vector<pair<lli, lli> > v[4*MAX];
void scanint(int &x)
{
register int c = gc();
x = 0;
for(;(c<48 || c>57);c = gc());
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
void Sieve(){
for (int i = 2; i < MAX; i += 2) sp[i] = 2;//even numbers have smallest prime factor 2
for (lli i = 3; i < MAX; i += 2){
if (!vv[i]){
sp[i] = i;
for (lli j = i; (j*i) < MAX; j += 2){
if (!vv[j*i]) vv[j*i] = true, sp[j*i] = i;
}
}
}
}
void build(int node, int l, int r)
{
if(l > r)return;
for(int i = l; i <= r; i++)
{
v[node].push_back(make_pair((lli)dp[i], (lli)i));
}
sort(v[node].begin(), v[node].end());
dpsum[node][0] = v[node][0].second*v[node][0].first;
for(int i = 1; i < v[node].size(); i++)
{
dpsum[node][i] = dpsum[node][i-1] + v[node][i].first*v[node][i].second;
}
if(l==r)return;
build(node*2, l, (l+r)/2);
build(node*2+1, (l+r)/2+1, r);
}
lli query(int node, int L, int R, int l, int r, int k)
{
if(l > R || r < L || L > R)return 0;
if(L >= l && R <= r)
{
int idx = lower_bound(v[node].begin(), v[node].end(), make_pair((lli)k+1,(lli)0)) - v[node].begin();
lli sum = 0;
int tt = v[node].size()-1;
sum = dpsum[node][tt] - dpsum[node][idx-1];
return sum;
}
lli aa = query(node*2, L, (L+R)/2, l, r, k);
lli bb = query(node*2+1, (L+R)/2+1, R, l, r, k);
return (aa+bb);
}
int main()
{
Sieve();
int n, q;
scanint(n);
scanint(q);
int a[n+1];
for(int i = 1; i <= n; i++)
scanint(a[i]);
map<int, int> ss;
for(int i = 1; i <= n; i++)
{
int temp = a[i];
while(temp > 1)
{
if(ss[sp[temp]] == 0){
dp[i] += sp[temp];ss[sp[temp]]=1;}
temp = temp/sp[temp];
}
ss.clear();
}
build(1, 1, n);
while(q--)
{
int l, r, k;
scanint(l);scanint(r);scanint(k);
printf("%lld\n",query(1, 1, n, l, r, k));
}
return 0;
}
avoid maps and you can precompute the sum of distinct primes for every number <= 10^7 . That gets AC . Code
Also you can get a RE if
idx
is 0 in your query function .oh thanks ! it was a map so I didn't care of (idx-1)<0 condition
my bad.