Cod sursa(job #2810992)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 30 noiembrie 2021 20:22:15
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>

#define int long long

using namespace std;

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

int n;
int a[1001001];
int b[1001001];
int c[1001001];
int aint[4004004];
int lazy[4004004];

void update(int nod, int st, int dr, int l, int r, int val)
{
    if(st > dr)
    {
        return ;
    }
    if(lazy[nod] != 0)
    {
        aint[nod] = lazy[nod];
        if(st != dr)
        {
            lazy[2 * nod] = lazy[nod];
            lazy[2 * nod + 1] = lazy[nod];
        }
        lazy[nod] = 0;
    }
    if(st > r || dr < l)
    {
        return ;
    }
    if(st >= l && dr <= r)
    {
        aint[nod] = val;
        if(st != dr)
        {
            lazy[2 * nod] = val;
            lazy[2 * nod + 1] = val;
        }
        return ;
    }
    int mijloc = (st + dr) / 2;
    update(2 * nod, st, mijloc, l, r, val);
    update(2 * nod + 1, mijloc + 1, dr, l, r, val);
}

int query(int nod, int st, int dr, int poz)
{
    if(lazy[nod] != 0)
    {
        aint[nod] = lazy[nod];
        if(st != dr)
        {
            lazy[2 * nod] = lazy[nod];
            lazy[2 * nod + 1] = lazy[nod];
        }
        lazy[nod] = 0;
    }
    if(st == dr)
    {
        return aint[nod];
    }
    int mijloc = (st + dr) / 2;
    if(poz <= mijloc)
    {
        return query(2 * nod, st, mijloc, poz);
    }
    else
    {
        return query(2 * nod + 1, mijloc + 1, dr, poz);
    }
}

int main()
{
    fin >> n >> a[1] >> b[1] >> c[1];
    for(int i = 2; i < n; i ++)
    {
        a[i] = (a[i - 1] * i) % n;
        b[i] = (b[i - 1] * i) % n;
        c[i] = (c[i - 1] * i) % n;
    }
    for(int i = 1; i < n; i ++)
    {
        int st = min(a[i], b[i]);
        int dr = max(a[i], b[i]);
        update(1, 1, n, st, dr, c[i]);
    }
    for(int i = 1; i < n; i ++)
    {
        fout << query(1, 1, n, i) << '\n';
    }
    return 0;
}