2
\$\begingroup\$

The problem is also known as GSS4. The exact detail can be seen here but I reached TLE.

You are given a sequence A of N(N <= 100,000) positive integers. There sum will be less than \$10^{18}\$. On this sequence you have to apply M (M <= 100,000) operations:

(A) For given x,y, for each elements between the x-th and the y-th ones (inclusively, counting from 1), modify it to its positive square root (rounded down to the nearest integer).

(B) For given x,y, query the sum of all the elements between the x-th and the y-th ones (inclusively, counting from 1) in the sequence. Input

Multiple test cases, please proceed them one by one. Input terminates by EOF.

For each test case:

The first line contains an integer N. The following line contains N integers, representing the sequence A1..AN. The third line contains an integer M. The next M lines contain the operations in the form "i x y".i=0 denotes the modify operation, i=1 denotes the query operation.

It's a classic segment tree--my very first one to be exact.

I asked my friend if I need Lazy Propagation but he said no. The only optimization that I did is if tree[X]=1, I don't update it anymore since sqrt(1) = 1

Is there a wrong implementation in my ST that causes TLE?

#include<stdio.h>
#include<math.h>

static unsigned long long int list[100000];
static unsigned long long int tree[264000];
int N, bigLevel;

void reset(){
    int K;
    for(K=0;K<100000;K++){
        list[K]=0;
    }
    for(K=0;K<264000;K++){
        tree[K]=0;
    }
}

void update(int from, int to){
    int start = ((int) pow(2,bigLevel-1)-1);
    int X, K;
    unsigned long long int J, diff;
    for(X=from-1;X<to;X++){
        //checking the root
        J= sqrt(tree[start+X]);
        diff = tree[start+X]-J;
        tree[start+X] = J;
        K = start+X;
        //if tree[start+X] is not 1, then we have some updates to do
        if(diff>0){
            //I understand that in ST, it's usually one indexed
            //but since it's my first time I create ST, I want to 
            //make it zero indexed
            while(K>0){
                K = (K-1)/2;
                tree[K] -= diff;
            }
        }
    }
}

void buildTree(){
    int level = 0;
    int X = N, J, c = 0;
    while(X>0){
        X /= 2;
        if(X%2 && X>1){
            c+=1;
        }
        level += 1;
    }
    if(c>0){
        level += 1;
    }
    bigLevel = level;
    // Building root
    int start = ((int) pow(2,level-1))-1;
    J = 0;
    for(X=start;X<((int) pow(2,level))-1;X++){
        tree[X] =  list[J];
        J += 1;
    }
    while(level>1){
        level-=1;
        start = ((int) pow(2,level-1))-1;
        J = 0;
        for(X=start; X<((int) pow(2,level))-1;X++){
            tree[X] = tree[(int) pow(2,level)-1 + (2*J)] + tree[(int) pow(2,level) + (2*J)];
            J += 1;
        }
    }
}

unsigned long long int query(int from, int to){
    unsigned long long int total = 0;
    int start = (int) pow(2,bigLevel-1)-1;
    int X, Y, Z, pos,gow;
    X = from-1;
    while(X<to){
        //printf("%llu %d\n",total,X);
        int pos = start + X;
        int cupid = X;
        int size = 1;
        int chunk = (int) pow(2,bigLevel-1);
        Z = X;
        gow = start;
        while(1){
            size *= 2;
            chunk /= 2;
            Y = Z / 2;
            // range = size(Z) <= from-1 < to-1 < size(Z+1)
            //Checking if not in range
            //If it's not in range, we climb one level too much
            if (!(X <= (size*Y)) || !((size*(Y+1)) < to-1)){
                total += tree[gow + Z];
                X = cupid+1; //isi
                break;
            }
            Z /= 2;
            gow /= 2;
            cupid = size*(Y+1)-1;
        }
    }
    return total;
}

int main(){
    int T=1;
    while(scanf("%d",&N)==1){
        printf("Case #%d:\n",T);
        int I, K;
        reset();
        for(I=0;I<N;I++){
            scanf("%d",&list[I]);
        }
        buildTree();
        scanf("%d",&K);
        int A,B,C;
        for(I=0;I<K;I++){
            scanf("%d %d %d",&A,&B,&C);
            if(A==0){
                update(B,C);
            }
            else{
                printf("%llu\n",query(B,C));
            }
        }
        printf("\n");
        T+=1;
    }
}

Edit:

  • It still TLE despite using cin cout that is not synchronized with Scanf.
  • People (who got AC) keep insisting that the problem is not in the square root, since it takes only 7 iterations.
\$\endgroup\$
  • \$\begingroup\$ This is supposed to be C++, right? So why did you bother with implementing a custom data structure? std::vector would have offered all you need. Anyway - the lesson of that challenge wasn't data handling, but efficiently calculating the squareroot of an integer. See e.g. stackoverflow.com/a/28976649/2879325 for a solution to the actual problem. \$\endgroup\$ – Ext3h Sep 18 '16 at 14:44
  • \$\begingroup\$ I am anticipating if I have to downgrade to C. Programming class can be cruel. \$\endgroup\$ – Realdeo Sep 19 '16 at 3:33
  • \$\begingroup\$ And the sqrt solution is compiler specific... \$\endgroup\$ – Realdeo Sep 19 '16 at 4:19
  • \$\begingroup\$ My friend hinted that I should use while(cin) instead of while(scanf) \$\endgroup\$ – Realdeo Sep 19 '16 at 5:40
  • \$\begingroup\$ your friend was correct. \$\endgroup\$ – pacmaninbw Sep 19 '16 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.