Cod sursa(job #2928632)

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

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

    int st, dr, val;
    void update_helper(int nod, int l, int r) {
        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);
        if (med < dr)
            update_helper((nod << 1) + 1, med + 1, r);
    }

    int poz;
    int query_helper(int nod, int l, int r) {
        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));
        else
            return std::max(aint[nod], query_helper((nod << 1) + 1, med + 1, r));
    }
}

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