I learned segment tree yesterday and tried to solve these following problems
399D - Красим стену
61E - Противник слаб
459D - Задача Пашмака и Пармиды
My solutions just barely pass the time limit.
81038127
81106193
81148972(needed faster I/O)
How can I strengthen this segment tree so that my solution fits into time limit completely.

1181D - Irrigation I have really a little idea about time complexity but I think this one of mine works in O(n logn). But, it is getting tle. Please help me to avoid the tle and make me understand why I got tle. sorry for my poor english.

55677921

I have solved this problem with binary search before. https://codeforces.com/contest/1156/problem/C But, I am trying to find out a deque solution but it fails at test 7.Why? 54565879 the algo is here. 1. sort the vector, 2. push every element at the end of the dq, 3. while pushing we would check if the difference between back and front element is greater than z(q.back() — q.front() >= z). if this condition is true, then increment the ans and pop the front and back elements. 4. when we finished traversing through the array, we get the answer.

what's wrong? please.

Seeking for an advice. Can I be a GM by 2020?

I began CP nearly for 5 months. but, for 2.5 months, I am not doing contests, just practicing problems sometimes and learning algorithms. Can I be a GM by early 2020?

I solved some quite hard(for me I think) these are-

https://codeforces.com/contest/1096/problem/D

https://codeforces.com/contest/1105/problem/E

https://codeforces.com/contest/1108/problem/E2

https://www.spoj.com/problems/WORDS1/

https://www.spoj.com/problems/TRIP/

please, how can I make it?

https://codeforces.com/contest/808/problem/D

unordered_map took me to tle but map took me to ac.

unordered_map submission https://codeforces.com/contest/808/submission/48371065

map submission https://codeforces.com/contest/808/submission/48371396

but we know generally unordered_map works in O(1) time where map works in O(log n) time. so, why this occurs. please.

when we are asked for solving knapsack problem where i-th item has exactly K_i copies then what to do without merging them into array.

for example, n = 2, V = {100, 30}, W = {17, 10}, K = {3,4}, S = 50. this means you can use item-1 3 times and item-2 4 times. then, i can merge the array as,

V = {100, 100, 100, 30, 30, 30, 30} and W = {17, 17, 17, 10, 10, 10, 10} and then using original knapsack. but that would take a lot of time--- O(S*sum of k).

how can i get a better solution.

please tell me why they show me wrong answer.

here

i used this technique. if a = 1, go right. if a = -1, go left, if b = 1, go up, if b = -1, go down.

used ara[64][64] to store 0 if it is not travelled and store 1 if it is travelled.

include<stdio.h>

include<string.h>

int main(){

int a,b,i,j,m,n,t,len,ara[64][64],p,q,r;

char s[130];

scanf("%d",&t);

for(i = 0; i < t; i++){

    scanf("%d %d\n", &m, &n);

    r = 0;

    gets(s);

    for(p = 0; p < 64; p++){

        for(q = 0; q < 64; q++){

            ara[p][q] = 0;
        }
    }
    ara[m][n] = 1;

    len = strlen(s);

    a = 0, b = 1;

    for(j = 0; j < len; j++){

        if(s[j] == 'F'){

            if(b == 1){

                n++;
            }
            else if(b == -1){

                n--;
            }
            else if(a == 1){

                m++;
            }
            else if(a == -1){

                m--;
            }
            if(ara[m][n] == 1){

                r++;
            }
            else{

                ara[m][n] = 1;
            }
        }
        else if(s[j] == 'R'){

            if(b == 1){

                b = 0;

                a = 1;
            }
            else if(b == -1){

                b = 0;

                a = -1;
            }
            else if(a == 1){

                a = 0;

                b = -1;
            }
            else if(a == -1){

                a = 0;

                b = 1;
            }
        }
        else{

            if(a == 1){

                a = 0;

                b = 1;
            }
            else if(a == -1){

                a = 0;

                b = -1;
            }
            else if(b == 1){

                b = 0;

                a = -1;
            }
            else if(b == -1){

                b = 0;

                a = 1;
            }
        }
    }
    printf("Case #%d: %d %d %d\n",i + 1,m,n,r);
}
return 0;

}

how can i find out a substring of minimum length having at least k times same character(for example k times a)of a string(please in C)

how can i solve #524C(div 2) without using adjacency matrix as i cannot form adjacency matrix due to large size of array

include<stdio.h>

int main(){

int l,r,n,m,i,j,x1,y1,x2,y2,x3,y3,x4,y4,s1,s2;

char a[1000000002][1000000002];

scanf("%d",&l);

for(r = 0; r < l; r++){

    scanf("%d %d",&n,&m);

    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

    scanf("%d %d %d %d",&x3,&y3,&x4,&y4);

    s1 = 0, s2 = 0;

    for(i = 1; i <= m; i++){

        for(j = 1; j <= n; j++){

            if((i + j) %2 == 0){

                a[i][j] = '0';/*white*/
            }
            else{

                a[i][j] = '1';/*black*/
            }
        }
    }
    for(i = x1; i <= x2; i++){

        for(j = y1; j <= y2; j++){

            a[i][j] = '0';
        }
    }
    for(i = x3; i <= x4; i++){

        for(j = y3; j <= y4; j++){

            a[i][j] = '1';
        }
    }
    for(i = 1; i <= m; i++){

        for(j = 1; j <= n; j++){

            if(a[i][j] == '0'){

                s1++;
            }
            else{

                s2++;
            }
        }
    }
    printf("%d %d\n",s1,s2);
}
return 0;

}

1076C - Meme Problem ~~~~~

include<stdio.h>

include<math.h>

int main(){

int a,t,i;

double y,z;

scanf("%d",&t);

for(i = 0; i < t; i++){

    scanf("%d",&a);

    if(a == 1 || a==2 || a==3){

        printf("N\n");
    }
    else{
        y = ((double)a + sqrt((double)a*(double)a - 4*(double)a))/2;

        z = ((double)a - sqrt((double)a*(double)a - 4*(double)a))/2;

        printf("Y %0.9lf %0.9lf\n",y,z);
    }
}
return 0;

} ~~~~~

gets AC in GNU C++11 but gets WA in C. though I wrote it in C syntax. how?

1036F - Relatively Prime Powers what's wrong with this code please?

include<stdio.h>

include<math.h>

/*function to find how many positive integers from 1 to n are power of m. as there are 3 numbers from 1 to 10 which is power of 2. so, ret_com(10,2.00) = 3*/

long long ret_com(long long n, double m){

return pow(n,(1/m)) - 1;

}

int main(){

long long a,x;

int i,j;

scanf("%d",&j);

for(i = 0; i < j; i++){

    scanf("%lld",&a);

/* i am trying to find how many numbers are power of a number. as gcd(k1,k2,k3,k4,.....) = 1, i have to find numbers of only single power(no square, no cube, no forth power and so on)*/

x = ret_com(a,2.00) + ret_com(a,3.00) + ret_com(a,5.00) + ret_com(a,7.00) + ret_com(a,11.00) + ret_com(a,13.00) + ret_com(a,17.00) + ret_com(a,19.00) + ret_com(a,23.00) + ret_com(a,29.00) + ret_com(a,31.00) + ret_com(a,37.00) + ret_com(a,41.00) + ret_com(a,43.00) + ret_com(a,47.00) + ret_com(a,53.00) + ret_com(a,59.00) - ret_com(a,6.00) - ret_com(a,10.00) - ret_com(a,14.00) - ret_com(a,15.00) - ret_com(a,21.00) - ret_com(a,22.00) - ret_com(a,26.00) - ret_com(a,33.00) - ret_com(a,34.00) - ret_com(a,35.00) - ret_com(a,38.00) - ret_com(a,39.00) - ret_com(a,46.00) - ret_com(a,51.00) - ret_com(a,55.00) - ret_com(a,57.00) - ret_com(a,58.00) + ret_com(a,30.00) + ret_com(a,42.00);/*using inclusion and exclusion principle.*/

    printf("%lld\n",a - x - 1);
}

return 0;

}

[problem:banh-me]

what's wrong with this code? please.

include<stdio.h>

include<math.h>

int main(){

long long k,l;

int a,b,i,p,q,j,ara[100003],t;

long long r,s1;

char s[100003];

l = pow(10,9) + 7;

scanf("%d %d\n",&a,&b);

gets(s);

t = 0;

for(i = 0; i < a; i++){

    if(s[i] == '1'){

        t++;
    }
    ara[i + 1] = t;
}
for(i = 0; i < b; i++){

    scanf("%d %d",&p,&q);

    s1 = ara[q] - ara[p - 1];

    r = ((long long)q - (long long)p + 1) - s1;

    k = pow(2,r)*((pow(2,s1)) - 1);

    k = k%l;

    printf("%lld\n",k);
}
return 0;

}

include<stdio.h>

include<math.h>

int main(){

int a,t,i;

double y,z;

scanf("%d",&t);

for(i = 0; i < t; i++){

    scanf("%d",&a);

    if(a == 1){

        printf("N\n");
    }
    else{
        y = ((double)a + sqrt((double)a*(double)a - 4*(double)a))/2;

        z = ((double)a - sqrt((double)a*(double)a - 4*(double)a))/2;

        printf("Y %0.9lf %0.9lf\n",y,z);
    }
}
return 0;

why this code shows wrong answer(1076 C)