Peaks

Peaks.cpp

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>


using namespace std;
//using namespace __gnu_pbds;


#define INF (1<<30)
#define INFll (1ll<<62)
#define F first
#define S second
#define MOD 1000000007ll
#define mkp(a, b) make_pair(a, b)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()


//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


#define FOR(I, A, B) for(int (I) = (A); (I) < (B); (I)++)
#define ROF(I, A, B) for(int (I) = (A); (I) >= (B); (I)--)


#define SQR(A) 1ll*(A)*(A)


const char array_sep[] = " ";
const char array_end[] = "";


const char pair_sep[] = " ";
const char pair_end[] = "";


const char map_sep[] = "->";
const char map_end[] = "\n";


//const int dx[] = {-1, 0, 1, 0};
//const int dy[] = {0, 1, 0, -1};
const int dx[] = {0, 1};
const int dy[] = {1, 0};
const int ddx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};


template<typename A> ostream & operator<<(ostream & os, const vector<A> & x)
{
    for(int i = 0; i < x.size(); i++)
        os << x[i] << array_sep;
    os << array_end;
    return os;
}

//template<typename A> ostream & operator<<(ostream & os, const set<A> & x)
//{
//    for(auto& y: x)
//        os << y << " ";
//    return os;
//}
//
//template<typename A, typename B> ostream & operator<<(ostream & os, const pair<A, B> & x)
//{
//    os << x.first << pair_sep << x.second << pair_end;
//    return os;
//}
//
//
template<typename A> istream & operator>>(istream & is, vector<A> & x)
{
    for(int i = 0; i < x.size(); i++)
        is >> x[i];
    return is;
}
//
//
//template<typename A, typename B> istream & operator>>(istream & is, pair<A, B> & x)
//{
//    is >> x.first >> x.second;
//    return is;
//}
//
//
//template<typename _key, typename _val> ostream & operator<<(ostream & os, map<_key, _val> & mp)
//{
//    os << "{\n";
//    for(auto it : mp)   // not for C++98 or earlier
//        os << "\t" << it.F << map_sep << it.S << map_end;
//    os << "}\n";
//    return os;
//}
//
//template<typename _key, typename _val> ostream & operator<<(ostream & os, unordered_map<_key, _val> & mp)
//{
//    os << "{\n";
//    for(auto it : mp)   // not for C++98 or earlier
//        os << "\t" << it.F << map_sep << it.S << map_end;
//    os << "}\n";
//    return os;
//}

//int start = clock();

//template<typename _response> void die(_response ans)
//{
//    cout << ans << endl;
////    cerr << (ld(clock()) - start) / CLOCKS_PER_SEC << endl;
//    exit(0);
//}

struct IN{} in;
#define cin in

inline bool delim(char &c) {
    return c == ' ' || c == '\n' || c == '\r' || c < 32;
}

template<typename T>
inline IN& operator>>(IN& t, T& a) {
    char buf;
    a = 0;
    while (delim(buf = getchar()));
    if (buf == '-') {
        t >> a;
        a = -a;
        return t;
    }
    while (true){
        a *= 10;
        a += buf - '0';
        if (delim(buf = getchar())) break;
    }
    return t;
}

inline IN& operator>>(IN& t, std::string& s) {
    char buf;
    s.clear();
    while (delim(buf = getchar()));
    do{
        s += buf;
    } while (!delim(buf = getchar()));
    return t;
}

inline IN& operator>>(IN& t, char& c) {
    while (delim(c = getchar()));
    return t;
}

struct query
{
    int v;
    int x;
    int k;
    int id;

    bool operator<(const query& to) const
    {
        return this->x < to.x;
    }

    query() {}
    query(int v, int x, int k, int id) : v(v), x(x), k(k), id(id) {}
};

struct Treap
{
    int key;
    int prior;
    int cnt;
    Treap* l;
    Treap* r;

    Treap(int x) : key(x), prior(rand()), cnt(1), l(NULL), r(NULL) {}
    Treap() : prior(rand()), cnt(1), l(NULL), r(NULL) {}
};

inline int sizeOf(Treap* root)
{
    return (root == NULL ? 0 : root->cnt);
}

inline void cnt(Treap* root)
{
    if(root == NULL) return;

    root->cnt = sizeOf(root->l) + sizeOf(root->r) + 1;
}

inline Treap* merge(Treap* l, Treap* r)
{
    if (l == NULL) return r;
    if (r == NULL) return l;

    if (l->prior > r->prior)
    {
        l->r = merge(l->r, r);
        cnt(l);
        return l;
    } else
    {
        r->l = merge(l, r->l);
        cnt(r);
        return r;
    }
}

inline pair<Treap*, Treap*> split(Treap* root, int key)
{
    if (root == NULL) return mkp((Treap *) NULL, (Treap *) NULL);

    if (root->key <= key)
    {
        pair<Treap*, Treap*> spl = split(root->r, key);
        root->r = spl.F;
        spl.F = root;

        cnt(spl.F);
        cnt(spl.S);

        return spl;
    } else
    {
        pair<Treap*, Treap*> spl = split(root->l, key);
        root->l = spl.S;
        spl.S = root;

        cnt(spl.F);
        cnt(spl.S);

        return spl;
    }
}

const int N = 200000;
Treap memes[N];
int sz = 0;

Treap* newTreap(int key)
{
    (memes + sz)->key = key;
    return (memes + sz++);
}

inline Treap* add(Treap* root, int x)
{
    pair<Treap*, Treap*> spl = split(root, x);
    return merge(merge(spl.F, newTreap(x)), spl.S);
}

inline Treap* add(Treap* root, Treap* x)
{
    pair<Treap*, Treap*> spl = split(root, x->key);
    return merge(merge(spl.F, x), spl.S);
}

inline Treap* unite(Treap* l, Treap* r)
{
    if (l == NULL) return r;
    if (r == NULL) return l;

    l = unite(l, r->l);
    l = unite(l, r->r);
    r->l = r->r = NULL;
    
    l = add(l, r);

    return l;
}

inline int find_Kth(Treap* root, int k)
{
    if (root == NULL)
        return -1;

    if (sizeOf(root->r) + 1 == k)
        return root->key;
    if (sizeOf(root->r) >= k)
        return find_Kth(root->r, k);

    return find_Kth(root->l, k - sizeOf(root->r) - 1);
}

int n;
vector<pair<int, pair<int, int > > > edges;
vector<query> qrs;
vector<int > h;
vector<int > p; // dsu ancestors
vector<Treap* > treaps;


inline int getp(int v)
{
    if (v == p[v]) return v;

    return p[v] = getp(p[v]);
}


inline void unite(int a, int b)
{
    a = getp(a);
    b = getp(b);

    if (a == b) return;

    if (sizeOf(treaps[a]) > sizeOf(treaps[b]))
    {
        p[b] = a;
        treaps[a] = unite(treaps[a], treaps[b]);
    } else
    {
        p[a] = b;
        treaps[b] = unite(treaps[b], treaps[a]);
    }
}

inline void add_edge(const pair<int, pair<int, int > >& e)
{
    unite(e.S.F, e.S.S);
}

int main()
{
//    srand((unsigned int) time(0));
    ios_base::sync_with_stdio(0);
//    cout << fixed << setprecision(8) << endl;
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//	freopen("errlog.log", "w", stderr);
#else
//    freopen("mroute.in", "r", stdin);
//    freopen("mroute.out", "w", stdout);
//    freopen("friends.in", "r", stdin);
#endif

    int m, q;
    cin >> n >> m >> q;
    h.resize(n);

    for(int i = 0; i < n; i++)
        cin >> h[i];

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        edges.push_back(mkp(c, mkp(a, b)));
    }

    sort(all(edges));

    qrs.reserve(q);

    for (int i = 0; i < q; i++)
    {
        int v, x, k;
        cin >> v >> x >> k;
        v--;
        qrs.push_back(query(v, x, k, i));
    }

    sort(all(qrs));

    p.resize(n);
    for (int i = 0; i < n; i++)
        p[i] = i;

    treaps.resize(n, NULL);
    for (int i = 0; i < n; i++)
        treaps[i] = add(treaps[i], h[i]);

    vector<int> ans(q, -1);

    int p = 0;

    for (int i = 0; i < q; i++)
    {
        while (p < m && edges[p].F <= qrs[i].x)
            add_edge(edges[p++]);

        int& v = qrs[i].v;
        int& k = qrs[i].k;
        int& id = qrs[i].id;

        ans[id] = find_Kth(treaps[getp(v)], k);
    }

    for(int i = 0; i < q; i++)
        printf("%d\n", ans[i]);

    return 0;
}