Edit: wrong algorithm. It's actually possible to end up with a cycle.

Currently there is a backlog of submissions waiting to be judged.
Results will be published when the submission queue is empty.
That will take approximately 1h.

I think that in less of a half hour, because in the judge, them published this:

"Currently there is a backlog of submissions waiting to be judged. Results will be published when the submission queue is empty. That will take approximately 1h."

120 can solved by prime factorization yes?

My solution is not that fast, but whatever...

Calculate DP[i][j] = min cost to make number j to number 1, by i step of operation (no lucky number). This takes O(maxA * lg(maxA) ^ 2) time.

for each query from a to b, we use at most one lucky number when making a move. With that observation, we can reduce each Q * M queries as a minimum y-intercept at position L_i, which can be solved with CHT.

This whole operation takes O(maxA * lg(maxA)^2 + QM + QT * lg(maxA)^2 ). It runs under 1.21s in analysis mode. code (In the contest it got 0 points because my code was quite bugged)

It should be log2(cnt). Also you can calculate cnt by sorting.

How did you solve it then?

In the code for problem C, you have a bad limit, because you have maxn = 500009 instead of maxn = 1048576, that is 2^20.

For problem B, change the size of s array by maxn*5 and get AC. I know, that's sad :'( Maybe with maxn*4 also works

There's actually a really good implementation of segment tree that uses 2*N memory: click. It's iterative, and therefore much faster than the recursion based segment tree. There are some problems where recursive segment trees are required. However, this should work on most problems.

For this problem you actually didn't need segment tree. There exists a very simple greedy solution (< 15 lines lol).

Omg!!! o_O

O (N) is compilation time here :D

My approach was the same as yours. After reading pllk's solution I also feel extremely stupid.

I used DSU to group the elements and applied greedy approach to find the minimum result.

First group all the elements by finding whose modulus gives 0, then go for 1,then 2 and so on.. till you have grouped all.

My Code

It's enough to change std::sort to countsort. I've modified your code a bit and it got accepted.

Modified code

I used the same approach and got AC(worked for p ≤ 10⁷).

It seems that you're sorting the edges in order to create the MST(please correct me if I'm wrong), this works in which wont work for p ≤ 10⁷, but since the weight of the edges are  ≤ 10⁷, you can create an array of vectors of size 10⁷ and add the edges to the corresponding vector, this way the complexity is .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
 
int x[100000], nxt[10000001], p[10000001];
vector<pair<int, int> > w[10000001];
 
int P(int v){
    if (p[v])return p[v] = P(p[v]);
    return v;
}
 
int main(){
    int n;
    scanf("%d", &n);
    f(i, 0, n)scanf("%d", x + i), nxt[x[i]] = x[i];
    sort(x, x + n);
    n = unique(x, x + n) - x;
    for (int i = 9999999; i >= 0; --i)if (!nxt[i])nxt[i] = nxt[i + 1];
    f(i, 0, n){
        int t = x[i], z = nxt[t + 1];
        if (z && z - t < t)w[z - t].push_back(make_pair(t, z));
        for (int j = t << 1; j <= 10000000; j += t){
            z = nxt[j];
            if (!z)break;
            if (z - j < t)w[z - j].push_back(make_pair(t, z));
        }
    }
    ll an = 0;
    int k = 0;
    f(i, 0, 10000000){
        vector<pair<int, int> > &v = w[i];
        int s = v.size();
        f(j, 0, s){
            int x = P(v[j].first), y = P(v[j].second);
            if (x == y)continue;
            an += i;
            p[y] = x;
            if (++k + 1 == n)break;
        }
        if (k + 1 == n)break;
    }
    printf("%lld\n", an);
}

With counting sort it can get accepted, http://ideone.com/iqBChI

UPD: Actually, I was bit late :(