laekov

前天晚上的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]);

}

}