Skip to content

Instantly share code, notes, and snippets.

@StarOrpheus
Created January 31, 2017 07:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save StarOrpheus/cdea557f96c4693a39b4fa847790bda5 to your computer and use it in GitHub Desktop.
Save StarOrpheus/cdea557f96c4693a39b4fa847790bda5 to your computer and use it in GitHub Desktop.
Peaks
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment