Cod sursa(job #1212764)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 25 iulie 2014 19:58:15
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int NMAX = 1000003;

struct RT_node {

    int value;
    bool update_pending;

};

RT_node RT[NMAX << 2];
int N, A, B, C, L, R;

void RT_update (const int &left, const int &right, const int &node) {

    if (RT[node].update_pending && left != right) {
        RT[node * 2].update_pending = RT[node * 2 + 1].update_pending = 1;
        RT[node].update_pending = 0;
        RT[node * 2].value = RT[node * 2 + 1].value = RT[node].value;
    }
    if (L <= left && right <= R) {
        RT[node].update_pending = 1;
        RT[node].value = C;
        return;
    }
    if (L > right || left > R)
        return;
    const int middle = left + right >> 1;
    RT_update (left, middle, node * 2);
    RT_update (middle + 1, right, node * 2 + 1);

}

void RT_DFS (const int &left, const int &right, const int &node) {

    if (RT[node].update_pending) {
        for (int i = left; i <= right; ++i)
            printf ("%d\n", RT[node].value);
        return;
    }
    if (left != right) {
        const int &middle = left + right >> 1;
        RT_DFS (left, middle, node * 2);
        RT_DFS (middle + 1, right, node * 2 + 1);
    }
    else
        printf ("0\n");

}

int main () {

    freopen ("curcubeu.in", "r", stdin);
    freopen ("curcubeu.out", "w", stdout);
    int i;

    scanf ("%d%d%d%d", &N, &A, &B, &C);

    for (i = 1; i < N; ++i) {
        L = min (A, B);
        R = max (A, B);
        RT_update (1, N - 1, 1);
        A = (1LL * A * (i + 1)) % N;
        B = (1LL * B * (i + 1)) % N;
        C = (1LL * C * (i + 1)) % N;
    }
    RT_DFS (1, N - 1, 1);

}