Cod sursa(job #2449506)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 19 august 2019 22:50:30
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

struct PatrickTree
{
    int valoare; // dusmanii stiu ca am valoarea !
    bool update; // Facem update-uri mai bune ca la cs :(
    PatrickTree()
    {
        valoare = -1;
        update = false;
    }
}aint[4000000];

int n, A, B, C, sol;

void Update(int nod, int st, int dr, int a, int b, int val)
{
    if (st >= a && dr <= b)
    {
        aint[nod].valoare = val;
        aint[nod].update = true;
        return;
    }
    if (st > b || dr < a)
    {
        return;
    }
    int mid = (st + dr) / 2;
    if (aint[nod].update == true)
    {
        aint[nod].update = false;
        aint[nod * 2].update = true;
        aint[nod * 2].valoare = aint[nod].valoare;
        aint[nod * 2 + 1].update = true;
        aint[nod * 2 + 1].valoare = aint[nod].valoare;
        aint[nod].valoare = -1;
    }
    Update(nod * 2, st, mid, a, b, val);
    Update(nod * 2 + 1, mid + 1, dr, a, b, val);

}

void Query(int nod, int st, int dr, int i)
{
    if (i >= st && i <= dr && aint[nod].valoare != -1)
    {
        sol = aint[nod].valoare;
        return;
    }
    if (i > dr || i < st)
    {
        return;
    }
    int mid = (st + dr) / 2;
    Query(nod * 2, st, mid, i);
    Query(nod * 2 + 1, mid + 1, dr, i);
}

int main()
{
    fin >> n >> A >> B >> C;
    Update(1, 1, n - 1, A, B, C);
    for (int i = 2; i < n; ++i)
    {
        A = (A * i) % n;
        B = (B * i) % n;
        C = (C * i) % n;
        Update(1, 1, n - 1, A, B, C);
    }
    for (int i = 1; i < n; ++i)
    {
        Query(1, 1, n - 1, i);
        fout << sol << "\n";
    }
    return 0;
}