前天晚上的best coder的题。
数据太弱暴力都放过去了，而且还是错的。当然我也太naive了TT。
我没管k<=10，直接硬上树状数组套平衡树，用二分搞的。然后数组开小了不开心啊。
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <set>
#include <memory.h>
using namespace std;
struct query {
int x, y, k, n;
};
struct tower {
int x, y, h;
};
inline bool cmpTower(const tower& a, const tower& b) {
return a. x < b. x;
}
inline bool cmpQuery(const query& a, const query& b) {
return a. x < b. x;
}
inline bool cmpP(int* a, int* b) {
return *a < *b;
}
const int maxn = 30009;
const int maxl = 19;
const int maxv = 1e9 + 9;
int n, m, *rx[maxn * 2], *ry[maxn * 2], mx, my;
int ans[maxn];
tower a[maxn];
query q[maxn];
int t[maxn * 2];
namespace sbt {
const int maxnd = maxn * maxl;
int sz[maxnd], ls[maxnd], rs[maxnd], vl[maxnd], tn;
void init() {
tn = 0;
sz[0] = 0;
}
inline void lRot(int& p) {
int q = rs[p];
rs[p] = ls[q];
ls[q] = p;
sz[q] = sz[p];
sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
p = q;
}
inline void rRot(int& p) {
int q = ls[p];
ls[p] = rs[q];
rs[q] = p;
sz[q] = sz[p];
sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
p = q;
}
inline void maintain(int& p, bool dir) {
if (dir) {
if (sz[ls[p]] > sz[rs[p]] + 1)
rRot(p);
}
else
if (sz[ls[p]] + 1 < sz[rs[p]])
lRot(p);
}
void ins(int& p, int v) {
if (!p) {
p = ++ tn;
ls[p] = 0;
rs[p] = 0;
sz[p] = 1;
vl[p] = v;
}
else {
if (v < vl[p])
ins(ls[p], v);
else
ins(rs[p], v);
++ sz[p];
maintain(p, v < vl[p]);
}
}
int cntLower(int p, int v) {
if (!p)
return 0;
else if (vl[p] <= v)
return sz[ls[p]] + 1 + cntLower(rs[p], v);
else
return cntLower(ls[p], v);
}
};
void dispNums() {
mx = 0;
sort(rx, rx + n + m, cmpP);
for (int i = 0, l = *rx[0] - 1; i < n + m; ++ i)
if (*rx[i] == l)
*rx[i] = mx;
else
l = *rx[i], *rx[i] = ++ mx;
my = 0;
sort(ry, ry + n + m, cmpP);
for (int i = 0, l = *ry[0] - 1; i < n + m; ++ i)
if (*ry[i] == l)
*ry[i] = my;
else
l = *ry[i], *ry[i] = ++ my;
}
void sov() {
sbt :: init();
memset(t, 0, sizeof(t));
for (int i = 0, j = 0; j < m; ++ j) {
while (i < n && a[i]. x <= q[j]. x) {
for (int p = a[i]. y; p <= my; p += (p & -p))
sbt :: ins(t[p], a[i]. h);
++ i;
}
int l = 0, r = maxv;
while (l < r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int p = q[j]. y; p; p -= (p & -p))
cnt += sbt :: cntLower(t[p], mid);
if (cnt >= q[j]. k)
r = mid;
else
l = mid + 1;
}
if (l == maxv)
ans[q[j]. n] = -1;
else
ans[q[j]. n] = l;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0; i < n; ++ i) {
scanf("%d%d%d", &a[i]. x, &a[i]. y, &a[i]. h);
rx[i] = &a[i]. x;
ry[i] = &a[i]. y;
}
for (int i = 0; i < m; ++ i) {
scanf("%d%d%d", &q[i]. x, &q[i]. y, &q[i]. k);
q[i]. n = i;
rx[i + n] = &q[i]. x;
ry[i + n] = &q[i]. y;
}
dispNums();
sort(a, a + n, cmpTower);
sort(q, q + m, cmpQuery);
sov();
for (int i = 0; i < m; ++ i)
printf("%d\n", ans[i]);
}
}