Submission #25905

# Submission time Handle Problem Language Result Execution time Memory
25905 2017-06-25T03:36:46 Z model_code Watering can (POI13_kon) C
100 / 100
506 ms 14460 KB
/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Konewka                                       *
 *   Autor:                Michal Adamczyk                               *
 *   Zlozonosc czasowa:    O((n + q) log n)                              *
 *   Zlozonosc pamieciowa: O(n)                                          *
 *   Opis:                 Rozwiazanie wzorcowe                          *
 *                         A - drzewo przedzialowe                       *
 *                         B - drzewo przedzialowe                       *
 *                                                                       *
 *************************************************************************/

#define INF (1000*1000*1000)
#define M 524288 // 2^19

inline int max(int a, int b) {
    return a > b ? a : b;
}

int N, K;
int dd[2*M]; // drzewa dojrzale
int nd_w[2*M]; // drzewa niedojrzale - wartosc w wezle
int nd_max[2*M]; // drzewa niedojrzale - max z synow + wartosc dla wezla

/** operacje na drzewach dojrzalych **/

/* wstawia dojrzale drzewo o numerze a */
void wstawDojrzale(int a) {
    int v = M + a;
    dd[v]++;
    while (v != 1) {
        v /= 2;
        dd[v] = dd[2*v] + dd[2*v+1];
    }
}

/* zwraca liczbe dojrzalych drzew na przedziale [a, b] */
int ileDojrzalych(int a, int b) {
    int va = M + a, vb = M + b;
    int wyn = dd[va];
    if (va != vb) wyn += dd[vb];
    while(va / 2 != vb / 2) {
        if (va%2 == 0) wyn += dd[va+1];
        if (vb%2 == 1) wyn += dd[vb-1];
        va /= 2, vb /= 2;
    }
    return wyn;
}

/** operacje na drzewach niedojrzalych */

inline void przesun_nizej(int v) {
    int ile = nd_w[v];
    nd_w[v] = 0;
    nd_w[2*v] += ile;
    nd_max[2*v] += ile;
    nd_w[2*v+1] += ile;
    nd_max[2*v+1] += ile;
}

/* ustawia wysokosc drzewa a na x */
void ustawWysokosc(int a, int x) {
    int v = M + a;
    nd_w[v] = x;
    nd_max[v] = x;
    while (v != 1) {
        v /= 2;
        nd_max[v] = nd_w[v] + max(nd_max[2*v], nd_max[2*v+1]);
    }
}

/* zwieksza o jeden wysokosci drzew na przedziale [p, k] */
void zwieksz(int v, int p, int k, int p_b, int k_b) {
    // v - indeks tablicy odpowiadający przedzialowi bazowemu [p_b, k_b]
    if (k < p_b || k_b < p || p_b > k_b)
        return;

    if (p <= p_b && k_b <= k) {
        nd_w[v]++;
        nd_max[v]++;
        return;
    }

    if(nd_w[v] > 0)
        przesun_nizej(v);

    int m = (p_b + k_b) / 2;
    zwieksz(2*v, p, k, p_b, m);
    zwieksz(2*v+1, p, k, m+1, k_b);

    nd_max[v] = max(nd_max[2*v], nd_max[2*v+1]);
}

/* znajduje dojrzale drzewa wśród wczesniej niedojrzalych (na przedziale [p, k])
 * dodaje je do struktury dla drzew dojrzalych oraz "usuwa" spośród niedojrzalych,
 * ustawiając ich wysokosc na -inf. */
void znajdzDojrzale(int v, int p, int k, int p_b, int k_b) {
    if(nd_max[v] < K || k < p_b || k_b < p || p_b > k_b)
        return;

    if(p_b == k_b) {
        wstawDojrzale(p_b);
        ustawWysokosc(p_b, -INF);
        return;
    }

    if(nd_w[v] > 0)
        przesun_nizej(v);

    int m = (p_b + k_b) / 2;
    znajdzDojrzale(2*v, p, k, p_b, m);
    znajdzDojrzale(2*v+1, p, k, m+1, k_b);
}

/** funkcje **/

void inicjuj(int n, int k, int *D) {
    N = n, K = k;
    int i;
    for (i = 0; i < N; ++i) {
        ustawWysokosc(i, D[i]);
    }
}

void podlej(int a, int b) {
    zwieksz(1,a,b,0,M-1);
}

int dojrzale(int a, int b) {
    znajdzDojrzale(1,a,b,0,M-1);
    return ileDojrzalych(a,b);
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 14460 KB Output is correct
2 Correct 0 ms 14460 KB Output is correct
3 Correct 0 ms 14460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 14460 KB Output is correct
2 Correct 3 ms 14456 KB Output is correct
3 Correct 0 ms 14456 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 63 ms 14460 KB Output is correct
2 Correct 46 ms 14460 KB Output is correct
3 Correct 63 ms 14460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 76 ms 14460 KB Output is correct
2 Correct 113 ms 14460 KB Output is correct
3 Correct 79 ms 14460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 126 ms 14456 KB Output is correct
2 Correct 89 ms 14460 KB Output is correct
3 Correct 166 ms 14456 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 283 ms 14460 KB Output is correct
2 Correct 166 ms 14456 KB Output is correct
3 Correct 169 ms 14460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 309 ms 14456 KB Output is correct
2 Correct 249 ms 14456 KB Output is correct
3 Correct 246 ms 14452 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 416 ms 14456 KB Output is correct
2 Correct 306 ms 14460 KB Output is correct
3 Correct 359 ms 14460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 489 ms 14456 KB Output is correct
2 Correct 419 ms 14456 KB Output is correct
3 Correct 379 ms 14456 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 506 ms 14456 KB Output is correct
2 Correct 399 ms 14460 KB Output is correct
3 Correct 439 ms 14456 KB Output is correct