Description
Statements
The hierarchical structure of the new office of Galactical Ministry of Bureacracy is very complicated. Office has 109 departments, numbered by sequential integers from 1 to 109.
Initially all departments are empty. Then two types of the events may happen:
- Arrival: new person is moved from old offices into some department. For this person are known his name and birthday. Assume this event is k-th arrival event for this department. Then person's local id is set to k.
- Departure: selected person in some department with local id k is moved out this department to the old offices.
The head of each department is defined by the following way:
- If some person is strictly older, than than all other people who are currently working in this department, he became the head of the department.
- In case of tie (two or more oldest employees), the one with least local id in this department became the head of the department.
The head of office is defined by the following way:
- If some person who currently works in new office is strictly older, than all other people who currently are working in the new office, this person is the head of the office.
- In case of tie person, who is working in the department with least number, have priority.
- In case of tie person with least local id on this department have priority.
You are asked to write a program which after each event prints name of the head of office and head of department, which is related to this event.
Input
First line of the input contains one integer n — number of events (1 ≤ n ≤ 105). Then n events follow.
First line of the event description contains one integer t — type of event (|t| = 1).
If t = 1, then new person is moved to the new office. Then second line contains one integer D — number of department, where new person is coming (1 ≤ D ≤ 109), next line contains non-empty string composed of no more than 10 lowercase English letters — name of the person, and next line contains his date of birth in Unified Decimal Galaxy Time format dd: mm: yyyy, where dd is for day, mm — for month and yyyy — for year, 00 ≤ dd, mm ≤ 99, 0001 ≤ yyyy ≤ 9999. You may assume that all names in the input file are pairwise distinct.
If t = - 1, then some person is moved back to the old offices. In this case second line contains two integers D and k — number of department and local id of person who is moved (1 ≤ D ≤ 109). It is guaranteed that k does not exceed total number of people who were moved to this department at the moment of event and that all k in the requests with t = - 1 are pairwise different.
Output
After each event print two space-separated strings: name of the head of the new office and name of head of department, which is related to this event. If new office or department contains no employees, printf "Vacant" instead.
Sample Input
8 1 10 rab 01:01:0001 1 1000000000 tor 02:01:0001 -1 10 1 1 10 tur 01:01:0001 -1 10 2 -1 1000000000 1 1 5 bor 99:99:9999 1 5 rot 99:99:9999
rab rab rab tor tor Vacant tur tur tor Vacant Vacant Vacant bor bor bor bor
Hint
Lets check what happened in the sample.
First event: in department 10 arrived new employee rab. He got local id 1 in this department, became the head of department and head of office.
Second event: in office 1000000000 arrived new employee tor. He got local id 1 in this department, became the head of department, but because rab's birthday is 01: 01: 0001, and tor's only 02: 01: 0001, tor is younger and does not became the head of office.
Third event: from department 10 removed employee with local id 1, i.e. rab. Department is empty, so we are printing "Vacant". In other departments only tor is working, so he became the head of office.
Fourth event: in department 10 arrived new employee tur. He got local id 2 in this department, became the head of department (because department was empty) and became the new head of the office, because his birthday is 01: 01: 0001, so he is older, than tor.
Fifth event: from department 10 removed employee with local id 2, i.e. tur. Department is empty, so we are printing "Vacant". In other departments only tor is working, so he became new head of office.
Sixth event: from department 1000000000 removed employee with local id 1, i.e. tor. Department is empty, so we are printing "Vacant". Office is empty, so we are printing "Vacant".
Seventh event: in department 5 arrived new employee bor. He got local id 1 in this department, became the head of department and head of office. Eight event: in department 5 arrived new employee rot. He got local id 2 in this department. His birthday is the as the bor's, but his local id is greater, so bor keeps his position as head of the department. Similarly, rot have same birthday as bor, they are working in same department, but his local id is greater, so bor keeps his position as head of the office.
题意：搬入、搬出新办公楼，新办公楼有1e9个部门，给出每个搬入人员的名字、生日和部门id，个人id是部门现有总人数，问当前操作结束后新办公楼的最年长者和当前操作人涉及的部门的最年长者名字
做法：set太特么6了，重载小于号就可以自动排序，map的键与值居然不仅可以是基本类型：可以是set,pair……
一个map用来维护部门id与人数
一个map用来维护部门id与部门人的set
一个set用来维护新办公室现有人集合
一个map用来映射（部门id,人id）->人
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
struct person
{
int dep;
char nm[30];
int time;
int id;
bool operator <(const person &oth)const
{
if(time!=oth.time)return time<oth.time;
if(dep!=oth.dep)return dep<oth.dep;
return id<oth.id;
}
};
map<int,int>cnt;
map<int,set<person> >deper;
set<person>tot;
map<pair<int,int>,person>per;
person p;
int main()
{
//freopen("cin.txt","r",stdin);
int n;
scanf("%d",&n);
while(n--)
{
int t;
scanf("%d",&t);
if(t==1)
{
scanf("%d%s",&p.dep,p.nm);
if(deper.find(p.dep)==deper.end())
{
deper[p.dep]=set<person>();
}
p.id=++cnt[p.dep];
int day,month,year;
scanf("%d:%d:%d",&day,&month,&year);
p.time=year*10000+month*100+day;
tot.insert(p);
per[make_pair(p.dep,p.id)]=p;
deper[p.dep].insert(p);
printf("%s %s\n",tot.begin()->nm,deper[p.dep].begin()->nm);
}
else
{
int d,k;
scanf("%d%d",&d,&k);
p=per[make_pair(d,k)];
tot.erase(p);
deper[d].erase(p);
printf("%s %s\n",tot.empty()?"Vacant":tot.begin()->nm,
deper[p.dep].empty()?"Vacant":deper[p.dep].begin()->nm);
}
}
return 0;
}
京公网安备 11010502036488号