Cod sursa(job #1735009)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 28 iulie 2016 17:52:49
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <cstdio>
int i,aa,bb,cc,n,ras;
struct andreea
{
    int cul,lazy;
}aint[4000005];
void update (int nod, int st, int dr, int x, int y, int val)
{
    int mij;
    if(aint[nod].lazy!=0)
    {
        aint[nod].cul=aint[nod].lazy;
        if(st<dr)
        {
            aint[nod*2].lazy=aint[2*nod+1].lazy=aint[nod].lazy;
        }
        aint[nod].lazy=0;
    }
    if(x>y||x>dr||y<st||st>dr)return;
    if(x<=st&&y>=dr)
    {
        aint[nod].cul=val;
        if(st<dr)
        {
            aint[nod*2].lazy=aint[nod*2+1].lazy=val;
        }
        return;
    }
    mij=(st+dr)/2;
    update(nod*2,st,mij,x,y,val);
    update(nod*2+1,mij+1,dr,x,y,val);
    if(aint[nod*2].cul==aint[nod*2+1].cul)aint[nod].cul=aint[nod*2].cul;
    else aint[nod].cul=-1;
}
void query(int nod, int st, int dr, int x, int y)
{
    int mij;
    if(x>y||x>dr||y<st||st>dr)return;
    if(aint[nod].lazy!=0)
    {
        aint[nod].cul=aint[nod].lazy;
        if(st<dr)
        {
            aint[nod*2].lazy=aint[2*nod+1].lazy=aint[nod].lazy;
        }
        aint[nod].lazy=0;
    }
    if(st==dr)
    {
        return;
    }
    mij=(st+dr)/2;
    query(nod*2,st,mij,x,y);
   query(nod*2+1,mij+1,dr,x,y);
}
void tsearch(int nod, int st, int dr, int poz)
{
    int mij;
    if(st>dr)return;
    if(st==dr)
        {printf("%d\n",aint[nod].cul);return;}
    mij=(st+dr)/2;
    tsearch(nod*2,st,mij,poz);
    tsearch(nod*2+1,mij+1,dr,poz);
}
int main()
{
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);
    scanf("%d%d%d%d",&n,&aa,&bb,&cc);
    n--;
    for(i=1;i<=n;i++)
    {
        if(i>1)
        {
            aa=(aa*i)%(n+1);
            bb=(bb*i)%(n+1);
            cc=(cc*i)%(n+1);
        }
        if(aa<bb)update(1,1,n,aa,bb,cc);
        else update(1,1,n,bb,aa,cc);
    }
    query(1,1,n,1,n);
    tsearch(1,1,n,1);
    return 0;
}