Cod sursa(job #3361780)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 28 iulie 2026 13:53:31
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;

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

struct event
{
    int a, b, c;
};

const int nmax = 1e6 + 5;

int t[nmax], h[nmax], nxt[nmax];

void init (int n)
{
    for (int i = 1; i <= n; i++)
    {
        t[i] = i;
        h[i] = 1;
        nxt[i] = i;
    }
}

int getroot (int nod)
{
    if (t[nod] != nod)
        t[nod] = getroot (t[nod]);
    return t[nod];
}

void unif (int x, int y)
{
    x = getroot (x);
    y = getroot (y);
    if (x == y)
        return;
    int mx = max(nxt[x], nxt[y]);
    if (h[x] < h[y])
        t[x] = y;
    else if (h[x] > h[y])
        t[y] = x;
    else
    {
        t[y] = x;
        h[x]++;
    }
    nxt[getroot (x)] = mx;
}

int n, v[nmax];

event query[nmax];

int main ()
{
    fin >> n >> query[1].a >> query[1].b >> query[1].c;
    n--;
    for (int i = 2; i <= n; i++)
    {
        query[i].a = query[i - 1].a * 1LL * i % (n + 1);
        query[i].b = query[i - 1].b * 1LL * i % (n + 1);
        query[i].c = query[i - 1].c * 1LL * i % (n + 1);
    }
    reverse (query + 1, query + n + 1);
    init (n + 1);
    for (int i = 1; i <= n; i++)
    {
        int a = min (query[i].a, query[i].b), b = max (query[i].a, query[i].b), c = query[i].c;
        int j = a;
        while (j <= b)
        {
            if (v[j])
            {
                j = nxt[getroot (j)] + 1;
                continue;
            }
            v[j] = c;
            if (v[j - 1])
                unif (j - 1, j);
            if (v[j + 1])
                unif (j, j + 1);
            j = nxt[getroot (j)] + 1;
        }
    }
    for (int i = 1; i <= n; i++)
        fout << v[i] << '\n';
    return 0;
}