Trening

http://amppz.tcs.uj.edu.pl/historia.php

X

Pamietajmy o:

  • gdb
  • .vimrc
  • Kacper miales mi przypomniec o materialach z poprzednich lat
  • Piotrek T. miales mnie kopnac w dupe za G.Pizze

Poprzedni trening

Mozna:

Zadania: http://zawody.ii.uni.wroc.pl/2002/zadania.phtml

countertree

// Grzegorz Wierzowiecki
// CounterTree - Drzewo Licznikowe
 
#include <cstdio>
 
class countertree{ public:
        long *t;
        long B;
        void init(long maxv){
#ifdef DEB
                printf("init(%ld)\n", maxv);
#endif
                for(B=1; B<maxv; B<<=1);
                t = new long [(B<<1)+1];
                for(int i=0; i<=(B<<1); i++)
                        t[i] = 0;
#ifdef DEB
                printf("init - end\n");
#endif
        };
        long less(long x){
                long wyn=0;
                int it, pop;
                for(pop=B+x, it=(B+x)>>1; it>0; pop=it, it>>=1){
                        if(pop!=(it<<1)) wyn += t[it<<1];
                };
                return wyn;
        };
        long add(long x){
                int it;
                for(it = x+B; it > 0; it>>=1)
                        t[it]++;
        };
        inline long count(long x){
                return t[x+B];
        };
        long calc(long from, long to){
#ifdef DEB
                printf("calc: count(%ld) + less(%ld) - less(%ld) = %ld + %ld - %ld \n",
                                to, to, from, count(to), less(to), less(from) );
#endif
                return count(to) + less(to) - less(from);
        };
        void print(){
                int i;
                for(i=0;i<=(B<<1);i++) printf("{%d,%ld}", i, t[i] );
                printf("\n");
        };
};
 
void doit(){
        int n,m,i;
        long *in, maxv=0,f,t;
        countertree ct;
        scanf("%d", &n);
        in = new long[n+1];
        for(int i=0; i<n; i++){
                scanf("%ld", &(in[i]) );
                if( in[i] > maxv ) maxv = in[i];
        };
        ct.init(maxv);
        for(i=0;i<n;i++) ct.add(in[i]);
        scanf("%d", &m);
        for(i=0;i<m;i++){
                scanf("%ld %ld", &f, &t);
#ifdef DEB
                printf("{%ld %ld}->", f ,t);
#endif
                printf("%ld\n", ct.calc(f,t));
        };
};
 
int main(){
        doit();
        return 0;
};

Dane Wejciowe

10
2
3
4
5
6
7
4
7
7
12
8
2 12
2 7
0 10
2 4
4 7
0 3
4 4
7 12
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License