Cod sursa(job #3240326)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 14 august 2024 01:29:20
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e6 + 5;

int N;
long long a, b, c;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
#define cin fin
#define cout fout

struct ArbInt
{
    int next_power_of_two(int n)
    {
        int p = 1;
        while (p <= n)
            p <<= 1;
        return p;
    }
    
    int offset;
    vector <int> v, arb, lazy;
    ArbInt(int n)
    {
        offset = 2 * next_power_of_two(n);
        
        arb.resize(2 * offset, 0);
        lazy.resize(2 * offset, 0);
        v.resize(n, 0);
    }
    
    inline void update_lazy(int node, int st, int dr)
    {
        arb[node] = lazy[node];
        if (st != dr)
        {
            lazy[2 * node] = lazy[node];
            lazy[2 * node + 1] = lazy[node];
        }
        lazy[node] = 0;
    }
    
    inline void _update(int node, int arb_st, int arb_dr, int q_st, int q_dr, int col)
    {

        if (q_dr < arb_st || q_st > arb_dr)
        {
            return;
        }
        
        if (lazy[node] != 0)
            update_lazy(node, arb_st, arb_dr);
            
        if (q_st <= arb_st && arb_dr <= q_dr)
        {
            lazy[node] = col;
            update_lazy(node, arb_st, arb_dr);
            return;
        }
        
        int mid = (arb_st + arb_dr) / 2;
        _update(2 * node, arb_st, mid, q_st, q_dr, col);
        _update(2 * node + 1, mid + 1, arb_dr, q_st, q_dr, col);
        
        return;
    }
    
    inline void update(int q_st, int q_dr, int col)
    {
        _update(1, 1, N - 1, q_st, q_dr, col);
    }
    
    inline void _dfs(int node, int st, int dr)
    {
        if (lazy[node] != 0)
            update_lazy(node, st, dr);
            
        if (st == dr)
        {
            v[st - 1] = arb[node];
            return;
        }
        
        int mid = (st + dr) / 2;
        
        _dfs(2 * node, st, mid);
        _dfs(2 * node + 1, mid + 1, dr);
        return;
    }
    
    inline void dfs()
    {
        _dfs(1, 1, N - 1);
        return;
    }
};

set <pair <int, int>> intrari[NMAX], iesiri[NMAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> a >> b >> c;
    
    // ArbInt arb = ArbInt(N - 1);
    // arb.update(min(a, b), max(a, b), c);
    
    intrari[min(a, b)].insert({1, c});
    iesiri[max(a, b)].insert({1, c});
    
    for (int i = 2 ; i <= N - 1 ; ++ i)
    {
        a = 1LL * a * i % N;
        b = 1LL * b * i % N;
        c = 1LL * c * i % N;
        
        // arb.update(min(a, b), max(a, b), c);
        
        intrari[min(a, b)].insert({i, c});
        iesiri[max(a, b)].insert({i, c});
    }
    
    int col = 0;
    set <pair <int, int>> active;
    for (int i = 1 ; i <= N - 1 ; ++ i)
    {
        col = 0;
        
        for (auto p: intrari[i])
            active.insert(p);
        
        if (!active.empty())
        {
            col = (*prev(active.end())).second;
        }
        
        for (auto p: iesiri[i])
            active.erase(p);
        
        cout << col << "\n";
    }
    
    // arb.dfs();
    // for (auto x: arb.v)
        // cout << x << '\n';
        
    return 0;
}