1291.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1291 on 2006-04-25 at 10:34:27 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int EN = 32768;

class Employee {
public:
	int id, pay, h;
	int boss, bid, sn;
	Employee(int cid = 0) : id(cid) {}
	void make();
};
void Employee::make() {
	scanf("%d %d %d", &id, &pay, &h);
	boss = -1; sn = 0;
}

bool idcmp(const Employee& e1, const Employee& e2) { return e1.id > e2.id; }
bool paycmp(const Employee& e1, const Employee& e2) { return e1.pay > e2.pay; }

int main()
{
	Employee e[EN];
	int en, qn;
	int t, T, i, j;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &en, &qn);
		for(i = 0; i < en; i++) e[i].make();
		sort(e, e+en, paycmp);
		for(i = 0; i < en; i++) {
			for(j = i-1; j >= 0 && e[j].h < e[i].h; j = e[j].boss);
			e[i].boss = j; e[i].bid = (j >= 0) ? e[j].id : 0;
		}
		for(i = en-1; i >= 0; i--)
			if(e[i].boss >= 0) e[e[i].boss].sn += e[i].sn+1;
		sort(e, e+en, idcmp);
		for(i = 0; i < qn; i++) {
			int qid; scanf("%d", &qid);
			Employee *be = lower_bound(e, e+en, Employee(qid), idcmp);
			printf("%d %d\n", be->bid, be->sn);
		}
	}
	
	return 0;
}