Cod sursa(job #2085749)

Utilizator amaliarebAmalia Rebegea amaliareb Data 10 decembrie 2017 17:34:52
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define iter set<pair<int, int> >:: iterator

using namespace std;
ifstream f("gossips.in");
ofstream g("gossips.out");
const int MaxN = 100005;
int n, m, q, n2, fth[MaxN];
pair<int, int> interv[MaxN];
vector<int> gr[MaxN];
set<pair<int, int> > aint[4 * MaxN];

void dfs(int node)
{
    interv[node].first = ++n2;
    //g << node << ' ';
    for (auto son: gr[node])
        if (!interv[son].first) dfs(son);
    interv[node].second = n2;
    //g << node << ' ';
}

inline void ins(int l, int r, set<pair<int, int> > &s)
{
    iter it = s.upper_bound({l, r});
    if (it != s.begin())
    {
        --it;
        if (it->second >= r) return;
        ++it;
    }
    while (it != s.end() && it->first < r)
    {
        iter aux = it;
        ++it;
        s.erase(aux);
    }
    it = s.insert({l, r}).first;
    ++l;
}

void update(int node, int l, int r, int poz, int updl, int updr)
{
    int mid = (l + r) / 2;
    ins(updl, updr, aint[node]);
    if (l == r) return;
    if (poz <= mid) update(2 * node, l, mid, poz, updl, updr);
    else update(2 * node + 1, mid + 1, r, poz, updl, updr);
}

bool query(int node, int l, int r, int ql, int qr, int a)
{
    int mid = (l + r) / 2;
    bool ok = 0;
    if (l >= ql && r <= qr)
    {
        if (aint[node].empty()) return 0;
        iter it = aint[node].lower_bound({interv[a].first, 0});
        if (it != aint[node].end() && it->first >= interv[a].first && it->second <= interv[a].second) ok = 1;
        if (it != aint[node].begin()) --it;
        if (it != aint[node].end() && it->first <= interv[a].first && it->second >= interv[a].first) ok = 1;
        return ok;
    }
    if (ql <= mid) ok = ok | query(2 * node, l, mid, ql, qr, a);
    if (qr > mid) ok = ok | query(2 * node + 1, mid + 1, r, ql, qr, a);
    return ok;
}

int main()
{
    f >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        fth[y] = x;
        gr[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) if (!fth[i]) dfs(i);
    for (; q > 0; --q)
    {
        int tip, a, b;
        f >> tip >> a >> b;
        if (tip == 1)
        {
            if (query(1, 1, n, interv[b].first, interv[b].second, a)) g << "YES\n";
            else g << "NO\n";
        }
        else
        {
            update(1, 1, n, interv[b].first, interv[a].first, interv[a].second);
        }
    }
    return 0;
}