Cod sursa(job #2449540)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 20 august 2019 00:22:01
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 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, maxx;

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);
}

void Build(int nod, int st, int dr)
{
    if (st == dr)
    {
        maxx = max(maxx, nod);
        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;
    }
    Build(nod * 2, st, mid);
    Build(nod * 2 + 1, mid + 1, dr);
}

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, min(A, B), max(A, B), C);
    }
    Build(1, 1, n - 1);
    for (int i = maxx - n + 2; i <= maxx; ++i)
    {
        if (aint[i].valoare == -1) aint[i].valoare = 0;
        fout << aint[i].valoare << "\n";
    }
    return 0;
}