3.29 网易雷火 第三题代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1050;
struct node{
    int l,r,u,d;
    int id,dep,pos;
}a[maxn];
string s;
map<string,int>mp;
int iID[maxn],wordID;
int check(int i,int j){
    if(a[i].d>=a[j].u||a[i].u<=a[j].d) return 0;
    else{
        if(a[i].r<=a[j].l||a[i].l>=a[j].r) return 0;
        else return 1;
    }
}
bool cmp(node x,node y){
    if(x.dep==y.dep){
        if(x.id==y.id) return x.pos<y.pos;
        return x.id<y.id;
    }
    return x.dep<y.dep;
}
int main() {
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>s;
        int x,y,w,h;
        cin>>x>>y>>w>>h;
        x*=2;y*=2;w*=2;h*=2;
        a[i].l=x-w/2;
        a[i].r=x+w/2;
        a[i].d=y-h/2;
        a[i].u=y+h/2;
        a[i].pos=i;
        if(s[0]=='I'){
            string ss;
            cin>>ss;
            if(mp[ss]==0) mp[ss]=++cnt;
            a[i].id=mp[ss];
        }
        else a[i].id=0;
    }
    for(int i=1;i<=m;i++){
        cin>>s;
        int x;
        cin>>x;
        iID[mp[s]]=x;
    }
    cin>>wordID;
    for(int i=1;i<=n;i++){
        if(a[i].id) a[i].id=iID[a[i].id];
        else a[i].id=wordID;
    }
    for(int i=1;i<=n;i++){
        int mx=0;
        vector<int>tmp;
        for(int j=1;j<i;j++){
            if(check(i,j)){
                if(a[i].id==a[j].id){
                    if(a[j].dep>mx){
                        tmp.clear();
                        mx=a[j].dep;
                        tmp.push_back(j);
                    }
                    else if(a[j].dep==mx){
                        tmp.push_back(j);
                    }
                }
                else{
                    if(a[j].dep+1>mx){
                        tmp.clear();
                        mx=a[j].dep+1;
                        tmp.push_back(j);
                    }
                    else if(a[j].dep+1==mx){
                        tmp.push_back(j);
                    }
                }
            }
        }
        if(mx==0) a[i].dep=1;
        else{
            a[i].dep=mx;
        }
    }
    sort(a+1,a+1+n,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i].id!=a[i-1].id) ans++;
    }
    cout<<ans<<endl;
	return 0;
}