12532 - Interval Product

All about problems in Volume 125. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12532 - Interval Product

Post by brianfry713 » Wed Nov 14, 2012 1:31 am

Input:

Code: Select all

100 16
12 0 81 -99 -55 -57 -29 72 -84 9 -36 81 -87 -23 -50 51 17 -17 -17 93 -43 7 59 -75 57 -24 30 34 100 29 0 11 -71 -70 12 -26 -26 83 97 -10 -59 -40 -80 -45 -13 -30 56 -97 3 -61 46 60 46 -45 35 -48 31 -36 87 -20 44 -64 91 73 -34 -47 97 40 86 93 80 -73 -98 50 -68 -11 -80 38 -8 -27 27 -62 84 -27 -7 18 -25 74 33 -89 -46 -74 -53 95 99 -36 -53 45 54 84
P 10 64
P 60 67
P 23 64
P 29 57
P 22 40
C 20 28
P 29 62
C 97 -14
P 2 13
C 2 30
P 4 11
C 35 -43
P 49 55
P 13 42
P 2 94
C 40 71
22 26
27 97 -74 63 10 -100 48 -12 -78 -23 -81 78 -56 85 -7 1 -68 51 -62 -16 -11 97
P 2 2
C 7 -42
C 18 -12
P 10 18
C 17 94
C 12 -69
C 2 -100
C 14 85
P 4 7
C 6 1
C 5 -36
P 1 3
C 20 -19
P 17 18
P 6 6
P 1 1
C 3 -36
P 6 12
P 4 16
P 1 13
C 10 35
C 10 59
C 20 -84
P 3 10
C 18 -1
P 1 8
87 56
-6 66 -78 -19 -20 13 -56 -90 -95 -81 43 -62 5 89 46 -37 100 85 -21 41 -58 33 -44 54 83 53 12 -17 83 -51 -34 -74 65 -61 7 95 2 1 56 8 21 -2 -4 -75 -63 -59 -62 -64 76 -33 27 -82 50 83 22 32 -15 85 -85 -83 -67 -69 -57 48 -30 51 43 73 -49 -2 -20 22 46 26 -3 83 18 35 -82 -7 -99 45 -39 52 -22 84 -17
C 58 68
C 4 51
C 65 -52
P 68 69
C 1 -62
P 3 9
P 16 22
P 4 41
P 20 40
P 52 55
C 84 -79
C 56 52
P 32 36
C 15 100
P 20 26
C 44 -78
P 55 59
C 11 98
P 19 43
C 10 -89
P 2 9
C 28 92
C 55 36
P 7 63
C 2 48
C 38 -34
P 11 43
P 19 36
P 6 19
P 31 36
P 32 42
P 13 28
C 47 -33
P 34 72
C 5 90
C 75 -26
P 46 46
P 19 24
P 11 13
P 9 43
P 64 74
C 70 89
P 16 16
P 38 86
C 28 72
C 72 -7
C 22 62
C 46 -54
C 50 -6
C 84 -68
C 70 -78
C 53 43
C 60 34
P 3 17
P 18 74
C 87 -62
3 45
-37 -96 -4
P 1 2
C 1 95
P 2 3
C 3 56
P 2 2
C 3 -4
P 1 2
P 1 1
C 2 -7
P 1 2
C 2 -34
P 1 2
P 2 2
C 2 -89
P 2 2
C 1 45
C 3 -90
C 3 93
P 1 2
P 1 1
P 1 2
P 2 2
P 2 3
P 1 1
P 1 1
P 2 3
C 1 -60
C 2 -94
C 1 -28
C 1 39
C 3 11
C 2 93
P 1 2
P 1 2
P 1 2
P 3 3
P 1 2
C 3 40
C 3 -13
C 2 55
C 2 100
P 1 3
P 1 1
P 1 2
P 1 2
87 51
88 19 -58 -93 -60 -48 47 18 -52 85 17 95 39 55 85 -11 53 -14 76 -6 -100 -88 63 77 -87 -90 -70 58 63 -82 -16 0 -12 26 -43 28 28 54 96 77 38 12 21 -23 -84 5 16 19 42 -9 -87 -8 3 76 -31 -33 37 -1 75 -51 -32 -41 -1 56 35 56 -67 -37 9 -72 90 -53 -10 10 -26 -44 66 90 75 -43 -70 38 -1 34 -36 68 -100
P 69 78
P 6 23
P 63 63
C 28 74
C 56 -99
P 2 42
P 36 53
P 17 18
C 63 60
P 6 15
C 78 74
C 5 73
C 67 -30
C 34 -27
P 10 10
C 41 -56
P 15 55
P 2 55
P 33 74
P 28 48
P 3 4
P 10 80
C 78 -21
C 28 -58
C 29 -13
P 13 15
P 15 22
P 66 66
P 2 2
P 14 80
C 79 51
C 71 -96
P 13 30
P 32 75
P 16 66
P 3 48
C 3 -66
C 60 -6
P 14 40
C 46 -94
P 12 42
P 9 22
C 7 35
C 73 36
C 51 51
P 9 23
C 74 -74
C 78 56
P 12 18
C 64 25
C 19 -98
85 64
-73 -92 33 12 29 0 -53 17 -96 49 -5 32 65 73 -14 41 -16 -34 -53 -11 -89 -48 -59 9 27 -100 92 29 51 10 -61 78 18 72 -61 -53 -28 -63 64 -74 86 -91 58 0 32 95 -59 -85 -90 -12 -46 -79 -10 -55 -20 -84 96 -29 46 46 81 85 -27 -52 6 -37 -5 28 0 -91 54 -15 -82 -38 35 50 -44 26 15 -34 -87 19 -63 -47 14
C 70 -80
P 3 3
C 53 0
P 31 80
P 27 80
P 21 30
C 13 -1
C 78 5
C 27 71
C 23 58
P 1 11
C 77 12
C 35 80
C 71 -54
C 65 58
C 52 -22
C 83 -84
P 4 40
C 16 -43
C 79 -72
P 15 71
P 18 36
P 40 58
P 3 4
C 23 60
C 42 -28
C 60 11
C 56 10
P 63 63
P 7 9
P 43 62
C 36 -10
P 22 52
P 7 76
P 19 42
P 13 73
P 8 27
C 57 -81
P 21 35
P 13 22
P 40 44
P 21 27
C 44 42
P 21 40
P 18 30
P 39 42
C 46 22
P 28 36
P 32 34
C 79 -77
P 1 22
C 63 97
P 54 60
C 65 -43
P 18 71
C 7 -88
C 16 28
P 16 30
C 41 -100
C 82 63
C 61 -24
C 20 66
P 14 49
C 75 33
29 50
15 44 23 -23 94 -85 55 16 -9 59 -24 71 59 -46 -11 -28 6 -11 -2 -65 -31 -37 61 -92 33 -28 99 -34 92
C 13 -42
P 12 26
P 11 15
P 16 16
C 2 58
P 2 25
C 1 35
C 6 55
P 2 10
P 17 19
P 13 14
C 13 -75
P 13 15
C 6 -15
P 2 8
P 3 7
P 1 7
P 5 16
P 3 13
C 29 -90
C 13 18
C 2 -19
C 8 77
C 13 10
C 20 89
C 18 23
C 17 -66
C 3 -81
P 5 21
P 4 15
P 5 8
C 18 -53
C 25 1
P 7 14
C 12 15
C 20 71
C 29 -9
P 11 11
C 6 -65
C 21 27
C 28 98
C 8 69
C 10 -35
C 16 10
C 9 37
C 10 -29
C 9 -70
P 3 5
P 1 3
C 28 47
86 79
20 37 -47 -62 33 34 4 -22 86 64 -99 -32 0 -61 22 22 -53 -82 2 46 -59 -19 6 62 52 51 22 -52 -78 -90 -34 -8 47 20 31 -21 -47 85 8 89 -2 9 -44 48 49 28 -31 46 46 71 -8 88 -98 48 -1 54 -2 -80 -98 -30 -70 -82 63 27 38 -57 57 41 78 -36 29 -25 23 36 -78 -79 -37 -58 68 60 -88 -91 -3 -86 57 96
P 5 23
P 36 71
P 9 18
C 44 80
P 35 73
C 34 82
P 57 74
P 28 34
P 66 72
P 43 79
C 55 -58
C 32 13
C 41 52
P 6 8
C 30 98
P 53 64
C 52 -23
C 85 73
C 62 -72
P 5 75
C 22 -73
C 36 -11
P 29 42
C 28 77
P 58 65
C 29 -66
C 54 100
P 6 24
P 26 51
P 7 77
C 42 16
C 76 29
P 3 10
P 32 85
P 17 31
C 17 -76
P 14 30
C 63 -51
P 13 13
C 2 50
C 43 42
P 12 12
C 12 -82
C 2 69
P 55 77
P 3 60
P 8 72
C 70 -87
P 1 4
P 37 72
C 31 -93
P 8 9
C 32 -52
P 56 66
P 61 69
P 12 17
P 27 67
C 58 -16
C 53 35
C 38 22
C 14 72
P 5 18
C 29 90
P 32 76
C 68 -62
P 36 70
C 56 -88
C 32 -46
P 9 31
P 3 30
P 49 85
C 74 -87
C 25 -57
C 7 -10
C 20 24
P 5 21
P 13 16
C 60 75
P 5 13
66 54
57 -5 51 -9 -87 -15 -46 -16 39 -3 -7 58 88 26 11 11 48 44 -8 46 71 83 6 -47 57 21 27 6 85 -25 30 42 70 -20 -68 34 65 -14 -83 3 34 10 -89 21 87 22 82 34 -35 -27 -71 86 -45 -15 -61 63 56 16 -82 41 91 48 -68 10 -73 -86
C 14 42
C 50 96
C 28 -94
P 22 39
P 41 58
P 8 37
P 5 5
C 64 -67
C 20 74
C 57 -16
P 2 3
C 30 -62
C 39 -41
P 3 4
P 2 62
P 11 54
P 5 8
P 1 29
C 39 42
C 46 75
C 47 -29
P 35 65
C 22 -51
C 25 84
P 2 12
C 7 84
C 12 28
P 19 55
P 44 58
P 6 15
P 13 29
P 5 17
P 23 33
C 4 -69
C 13 26
P 5 8
P 29 33
C 15 15
C 6 100
C 19 -78
C 45 16
C 59 -92
P 37 42
C 45 -38
P 6 10
C 65 52
C 32 -1
C 60 20
C 7 57
P 20 34
P 6 11
P 18 20
C 13 5
C 25 26
90 100
-79 34 83 23 53 7 72 -84 -50 -9 46 61 98 -76 2 98 25 -57 -77 -9 33 79 -35 -97 -17 77 82 59 50 0 -91 21 84 92 -57 36 -1 -86 3 -1 5 99 -90 -47 73 -38 -50 -53 5 -76 38 88 53 53 91 86 29 23 45 -72 -78 54 49 -95 -5 42 -9 44 6 94 94 61 42 -97 -87 14 -85 -86 61 -30 89 -52 -42 41 -100 99 26 -21 21 -80
P 12 70
C 53 -2
C 3 40
C 14 -17
C 45 -75
C 90 -11
C 32 -50
C 73 -2
C 11 -51
C 13 -22
P 40 87
P 8 24
P 7 42
P 9 51
P 3 28
P 37 86
P 49 85
C 25 -97
C 24 73
C 38 -82
C 34 -15
C 57 -25
P 14 16
P 11 40
P 6 26
C 5 72
C 90 -17
C 72 -61
C 65 48
C 88 -94
P 39 62
C 80 -16
C 57 -7
C 6 -96
C 84 51
P 4 80
C 36 -35
P 7 90
C 35 -74
C 54 -73
P 4 41
P 13 22
C 59 27
C 69 -95
C 30 16
P 39 40
C 80 -19
P 34 45
P 14 80
P 43 89
C 60 86
P 21 60
P 8 14
C 77 -88
C 42 -40
P 73 84
C 85 87
P 11 43
P 26 27
P 1 7
C 7 43
C 29 70
C 42 -16
P 12 16
C 12 -90
P 21 54
P 29 49
P 2 33
P 3 6
C 31 -37
P 6 81
C 69 84
C 40 39
P 5 48
C 18 62
P 23 37
C 82 -70
P 3 17
C 82 85
C 25 99
P 51 81
P 3 8
C 52 45
P 11 11
P 38 84
P 39 79
C 33 -39
P 29 46
P 70 73
C 27 -6
C 69 -32
P 3 13
P 68 68
C 62 -49
C 56 11
P 26 55
P 39 50
P 62 74
P 45 47
C 44 95
AC output:

Code: Select all

0+00000++00
++++-+++-+--
------++++-++---++----++-+--
++--+-----+---++-+++++-+++
---0--++00+0+0+-++0-00000+++
+00+000+0+-+000-0++-0-+++++0+0--
-+-++++-+++---+---++
0+0----+-+0+-0-0-+++0--00++-++0+0++00+000
-+----+++-++--++-----++--
0--00+-+-0-+000---++++++++++-----++-+--+-+-+-+--
Check input and AC output for thousands of problems on uDebug!

ediuzx
New poster
Posts: 2
Joined: Wed Nov 21, 2012 8:25 am

Re: 12532 - Interval Product

Post by ediuzx » Wed Nov 21, 2012 8:29 am

i am getting WA pls some help, even i get the same as the example

ACC
Last edited by ediuzx on Thu Dec 13, 2012 1:35 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12532 - Interval Product

Post by brianfry713 » Fri Nov 30, 2012 9:40 am

Increase the size of st, 3*N is more than big enough, 2*N is too small. In my code I used an array of a little larger than 1<<18.
Check input and AC output for thousands of problems on uDebug!

jrbustosm
New poster
Posts: 6
Joined: Tue Oct 09, 2012 9:18 pm

Re: 12532 - Interval Product

Post by jrbustosm » Wed Dec 05, 2012 11:15 pm

I do not know if it is legal to put external links, but the file is very large:

https://raw.github.com/jrbustosm/uva-so ... duct/input

the output is:

https://raw.github.com/jrbustosm/uva-so ... uct/salida

ediuzx
New poster
Posts: 2
Joined: Wed Nov 21, 2012 8:25 am

Re: 12532 - Interval Product

Post by ediuzx » Thu Dec 13, 2012 1:34 am

thanks for the help, finally i get ACC

mazid
New poster
Posts: 6
Joined: Sun Dec 23, 2012 9:16 am

12532 - Interval Product TLE

Post by mazid » Sat Apr 06, 2013 7:25 pm

Getting TLE :(
How can I improve my code???

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
    int n,k,i,j,mult,c;
    int N[100000],a,b;
    char ch[2],ans[100000];

    while(scanf("%d %d",&n,&k)!=EOF)
    {
        c=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&N[i]);
        }
        for(i=0;i<k;i++)
        {
            scanf("%s %d %d",&ch,&a,&b);
            if(!strcmp(ch,"C")) N[a-1]=b;
            else
            {
                mult=0;
                int x=a-1,y=b-1;
                for(j=x;j<=y;j++)
                {
                    if(N[j]<0) mult++;
                    else if(N[j]==0) break;
                }
                if(j<=y&&N[j]==0) ans[c]='0';
                else if(!(mult%2)) ans[c]='+';
                else ans[c]='-';
                c++;
            }
            memset(ch,'\0',sizeof(ch));
        }
        printf("%s\n",ans);
        memset(ans,'\0',sizeof(ans));
    }

    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12532 - Interval Product TLE

Post by brianfry713 » Tue Apr 09, 2013 11:34 pm

Don't use memset(), if you want to print ans as a string, just null terminate the last char.
Check input and AC output for thousands of problems on uDebug!

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

Re: 12532 - Interval Product TLE

Post by alimbubt » Sat Apr 27, 2013 9:03 pm

Sample Input:

Code: Select all

10 15
100 100 98 87 16 -99 12 77 12 0
C 3 -19
C 4 99
C 8 0
P 2 5
P 5 9
P 1 3
C 6 -12
C 1 -1
P 4 4
P 10 10
P 1 10
P 4 7
P 5 8
P 3 9
P 2 4
Sample Output:

Code: Select all

-0-+00-00-
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 12532 - Interval Product TLE

Post by shuvokr » Sun Oct 06, 2013 9:55 pm

Loading ...

Code: Select all

enjoying life ..... 

Post Reply

Return to “Volume 125 (12500-12599)”