Cod sursa(job #3247377)

Utilizator paull122Paul Ion paull122 Data 7 octombrie 2024 14:43:58
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

#define VMAX 50000
#define NMAX 1000000

#define LOG 22
#define INF (long long)(1e9)
#define MOD 1000000007
#define ll long long int

#define ADD 1e9

#define NIL 0




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

struct query
{
    int a,b,c;
} q[NMAX+1];

int dr[NMAX+1],n,res[NMAX+1],st[NMAX+1];

int Parent[NMAX+1];
int Find(int x)
{
    if(x!=Parent[x])
    {
        Parent[x] = Find(Parent[x]);
    }
    return Parent[x];
}

void Unite(int x,int y)
{
    x = Find(x);
    y = Find(y);

    res[y]=res[x];
    Parent[y]=x;
}
int main()
{
    fin >> n;
    fin >> q[1].a >> q[1].b >> q[1].c;
    for(int i=2;i<n;i++)
    {
        q[i].a = i*1ll*q[i-1].a%n;
        q[i].b = i*1ll*q[i-1].b%n;
        q[i].c = i*1ll*q[i-1].c%n;
    }
    for(int i=1;i<=n;i++)
    {
        dr[i]=i+1;
        st[i]=i-1;
        Parent[i]=i;
        res[i]=0;
    }
    dr[n]=0;
    for(int i=n-1;i>=1;i--)
    {
        int l = min(q[i].a,q[i].b);
        int r = max(q[i].a,q[i].b);
        int c = q[i].c;

        int j = l;
        if(res[j])
        {
            j=dr[j];
        }
        if(j<=r && j)
        {
            res[j]=c;
        }
        while(dr[j]<=r && dr[j])
        {
            Unite(j,dr[j]);
            j=dr[j];
        }

        dr[st[l]] = dr[j];
        st[dr[j]] = st[l];
    }
    for(int i=1;i<n;i++)
    {
        fout << res[i] << "\n";
    }
}