Pagini recente » Cod sursa (job #3361324) | Cod sursa (job #3361550) | Cod sursa (job #3361316) | Cod sursa (job #3361552) | Cod sursa (job #3361779)
#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;
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;
}