12532, C++ (gcc) - rextester

Language: Layout:

#include <iostream>
#include <vector>
#define MAXTAM 100000

using namespace std;

vector<int> ft(MAXTAM), ftC(MAXTAM);
vector<int> entradas;

int LSOne(int n)
{
    return n&(-n);
}

void actualizaN(int n,int valor)
{
    while(n<MAXTAM)
    {
        ft[n]+=valor;
        n+=LSOne(n);
    }
}

int consultaN(int a)
{
    int suma;
    suma = 0;
    
    while(a)
    {
        suma+=ft[a];
        a-=LSOne(a);
    }
    
    return suma;
}

void actualizaC(int n,int valor)
{
    while(n<MAXTAM)
    {
        ftC[n]+=valor;
        n+=LSOne(n);
    }
}

int consultaC(int a)
{
    int suma;
    suma = 0;
    
    while(a)
    {
        suma+=ftC[a];
        a-=LSOne(a);
    }
    
    return suma;
}

int main()
{
    int N, K;
    int num;
    char inst;
    int ind, val;
    int cc, cn;
    int a, b;
    
    while(cin>>N)
    {
        entradas.clear();
        entradas.push_back(0);
        cin>>K;
        for(int i=1; i<=N; i++)
        {
            cin>>num;
            
            entradas.push_back(num);
            
            if(num<0)
                actualizaN(i, 1);
            
            if(num==0)
                actualizaC(i, 1);
        }
        
        /*
                cout<< "\nEntradas I: ";  
                for(auto a: entradas)
                    cout<< a;
                cout<<"\n";
        */
        
        for(int i=1; i<=K; i++)
        {
            cin>>inst;
            cin>>ind;
            cin>>val;            
            
            if(inst == 'C')
            {
                if(entradas[ind]<0 and val>0)
                    actualizaN(ind, -1);                
                else if(entradas[ind]>0 and val<0)
                    actualizaN(ind, +1);
                else if(entradas[ind]==0 and val!=0)
                    actualizaC(ind, -1);                
                else if(entradas[ind]!=0 and val==0)
                    actualizaC(ind, +1);  
                    
                    else if(entradas[ind]==0 and val<0)
                    {
                        actualizaN(ind, +1); 
                        actualizaC(ind, -1); 
                    } 
                    else if(entradas[ind]<0 and val==0)
                    {
                        actualizaN(ind, -1); 
                        actualizaC(ind, +1); 
                    }     
                    
                entradas[ind] = val;
                /*
                cout<< "\nConsulta N: ";
                for(int i=1; i<=N; i++)
                    cout<< consultaN(i);
                cout<< "\nConsulta C: ";    
                for(int i=1; i<=N; i++)
                    cout<< consultaC(i);
                cout<< "\nEntradas: ";  
                for(auto a: entradas)
                    cout<< a;
                cout<<"\n";*/
                    
            }
                
            if(inst == 'P')
            {
                if(ind==1)
                {
                    cc = consultaC(val);
                    cn = consultaN(val); 
                }else
                {
                    cc = consultaC(val) - consultaC(ind-1);
                    cn = consultaN(val) - consultaN(ind-1); 
                }
                
                if(cn%2 == 0 and cc==0)
                    cout<<"+";
                else if(cn%2 == 1 and cc==0)
                    cout<<"-";
                else if(cc>0)
                    cout<<"0";
                
            }            
        }
        printf("\n");
        for(int i=0; i<MAXTAM; i++)
        {
            ft[i]=0;
            ftC[i]=0;
        }            
    }
}

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

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 0.53 sec, absolute running time: 0.08 sec, cpu time: 0.02 sec, memory peak: 3 Mb, absolute service time: 0,63 sec