Cod sursa(job #777716)

Utilizator beelzebubOga Tatsumi beelzebub Data 13 august 2012 10:17:11
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.42 kb
#include<stdio.h>
#include<set>
#include<vector>
using namespace std;

#define pb push_back
#define NMAX 100005

vector<int> v[NMAX];
set<int> aint1[3 * NMAX],aint2[3 * NMAX];
set<int> ::iterator it;
char viz[NMAX];
int stanga[NMAX],dreapta[NMAX];
int nr,n,m,q;

inline void dfs(int nod)
{
        int i,lim = v[nod].size();
        stanga[nod] = ++nr;
        for(i = 0; i < lim; i++)
                dfs(v[nod][i]);
        dreapta[nod] = nr;
}

inline void Update1(int n, int st, int dr, int a, int b, int val)
{
    //    printf("Update1: nodul %d intervalul %d %d si vreau sa pun in intervalul %d %d valoarea %d\n\n",n,st,dr,a,b,val);
        if(a <= st && dr <= b)
        {
                aint1[n].insert(val);
             /*   printf("//////////////// %d %d ",n,val);
                it = aint1[n].lower_bound(3);it++;
                val = *it;
                printf("%d\n",val);*/
                return ;
        }
        int mij = (st + dr) /  2;
        if(a <= mij)
                Update1(2 * n, st, mij, a, b, val);
        if(b > mij)
                Update1(2 * n + 1, mij + 1, dr, a, b, val);
}

inline void Update2(int n, int st, int dr, int poz, int val)
{
       // printf("Update2: nodul %d intervalul %d %d si vreau sa pun pe pozitia %d valoarea %d\n\n",n,st,dr,poz,val);
        aint2[n].insert(val);
        if(st == dr)
                return ;
        int mij = (st + dr) / 2;
        if(poz <= mij)
                Update2(2 * n, st, mij, poz, val);
        else
                Update2(2 * n + 1, mij + 1, dr, poz, val);
}

inline int Query1(int n, int st, int dr, int poz, int valmin, int valmax)
{
       // printf("Query1: nodul %d intervalul %d %d si vreau sa aflu pentru pozitia %d o valoare din %d %d\n\n",n,st,dr,poz,valmin,valmax);
        int val = aint1[n].size();
        if(val > 0)
        {
                it = aint1[n].lower_bound(valmax + 1); it++;
                val = *it;
                if(valmin <= val && val <= valmax)
                {
                      //  printf("Si a gasit\n");
                        return 1;
                }
        }
        if(st == dr)
                return 0;
        int mij = (st + dr) / 2;
        if(poz <= mij)
                return Query1(2 * n, st, mij, poz, valmin, valmax);
        return Query1(2 * n + 1, mij + 1, dr, poz, valmin, valmax);
}

inline int Query2(int n, int st, int dr, int a, int b, int valmin, int valmax)
{
     //   printf("Query2: nodul %d intervalul %d %d si vreau sa aflu pentru intervalul %d %d o valoare din %d %d\n\n",n,st,dr,a,b,valmin,valmax);
        if(a <= st && dr <= b)
        {
                int val = aint2[n].size();
                if(!val)
                        return 0;
                it = aint2[n].lower_bound(valmax + 1);it++;
                val = *it;
                if(valmin <= val && val <= valmax)
                {
                 //       printf("Si a gasit\n");
                        return 1;
                }
                return 0;
        }
        int mij = (st + dr) / 2,r1 = 0,r2 = 0;
        if(a <= mij)
                r1 = Query2(2 * n, st, mij, a, b, valmin, valmax);
        if(b > mij)
                r2 = Query2(2 * n + 1, mij + 1, dr, a, b, valmin, valmax);
        return (r1|r2);
}

int main ()
{
        int i,a,b,tip,ans1,ans2;

        freopen("gossips.in","r",stdin);
        freopen("gosspis.out","w",stdout);

        scanf("%d%d%d",&n,&m,&q);

        for(i = 1; i <= m; i++)
        {
                scanf("%d%d",&a,&b);
                v[a].pb(b);
                viz[b] = 1;
        }

        for(i = 1; i <= n; i++)
                if(!viz[i])
                        dfs(i);
        for(i = 1; i <= q; i++)
        {
                scanf("%d%d%d",&tip,&a,&b);
                if(tip == 1)
                {
                        ans1 = Query1(1,1,n,stanga[a],stanga[b],dreapta[b]);
                        ans2 = Query2(1,1,n,stanga[a],dreapta[a],stanga[b],dreapta[b]);
                        if(ans1 || ans2)
                                printf("YES\n");
                        else
                                printf("NO\n");
                }
                else
                {
                        Update1(1,1,n,stanga[a],dreapta[a],stanga[b]);
                        Update2(1,1,n,stanga[a],stanga[b]);
                }
        }

        return 0;
}