Cod sursa(job #2928628)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 23 octombrie 2022 15:34:00
Problema Curcubeu Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#define query(poz) query_helper(1, 1, AINT::offset, poz)
#define update(st, dr, val) update_helper(1, 1, AINT::offset, st, dr, val)

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

typedef long long ll;

int const nmax = 1e6;
int cul[nmax + 5];

namespace AINT {
    int const offset = (1 << 20);
    int aint[(offset << 1) + 5];

    void init() {
        for (int i = 0; i <= (offset << 1); i++)
            aint[i] = 0;
    }

    void update_helper(int nod, int l, int r, int st, int dr, int val) {
        if (st <= l && r <= dr) {
            aint[nod] = std::max(aint[nod], val);
            return;
        }
        int med = (l + r) >> 1;
        if (st <= med)
            update_helper((nod << 1), l, med, st, dr, val);
        if (med < dr)
            update_helper((nod << 1) + 1, med + 1, r, st, dr, val);
    }

    int query_helper(int nod, int l, int r, int poz) {
        if (l == r)
            return aint[nod];
        int med = (l + r) >> 1;
        if (poz <= med)
            return std::max(aint[nod], query_helper((nod << 1), l, med, poz));
        else
            return std::max(aint[nod], query_helper((nod << 1) + 1, med + 1, r, poz));
    }
}

int main() {
    AINT::init();
    int n;
    fin >> n;
    ll a, b, c;
    fin >> a >> b >> c;
    AINT::update(a, b, 1);
    cul[1] = c;
    for (int i = 2; i < n; i++) {
        a = (a * i) % n;
        b = (b * i) % n;
        c = (c * i) % n;
        AINT::update(std::min(a, b), std::max(a, b), i);
        cul[i] = c;
    }
    cul[0] = 0;
    for (int i = 1; i < n; i++)
        fout << cul[AINT::query(i)] << "\n";
    return 0;
}