Cod sursa(job #3128846)

Utilizator SorinBossuMarian Sorin SorinBossu Data 11 mai 2023 09:00:07
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <stack>
#include <fstream>
#include <stack>
using namespace std;
ifstream in("curcubeu.in");
ofstream out("curcubeu.out");
int p[1000001], n, mod, a[1000001];
struct query
{
    query(int a1, int b1, int c1):a(a1), b(b1), c(c1){}
    int a, b, c;
};
stack<query> q;

void add(int n)
{
    p[n] = n, a[n] = 0;
}

int find_set(int n)
{
    if ( p[n] == n )
        return n;
    return p[n] = find_set(p[n]);
}

int main()
{
    int a1, b1, c1;

    in >> n >> a1 >> b1 >> c1;
    mod = n;
    n--;
    q.emplace(a1, b1, c1);
    add(1);
    add(n+1);
    for ( int i = 2; i <= n;  ++i )
    {
        add(i);
        int a, b, c;
        query q1 = q.top();
        a = 1LL*q1.a%mod*i%mod;
        a%=mod;
        b = 1LL*q1.b%mod*i%mod;
        b%=mod;
        c = 1LL*q1.c%mod*i%mod;
        c%=mod;
        if ( b < a )
            swap(b, a);
        q.emplace(a, b, c);
    }
    while(!q.empty())
    {
        query q1 = q.top();
        q.pop();
        int poz = q1.a;
        while(poz <= q1.b )
        {
            if ( p[poz] == poz )
                p[poz] = poz+1, a[poz] = q1.c;
            poz = find_set(poz);
        }
    }
    for ( int i = 1; i <= n; ++i )
        out << a[i] << "\n";

    return 0;
}