1650. Billionaires(线段树)

时间:2024-01-18 10:50:26

1650

简单题 线段树的单点更新 就是字符串神马的 有点小繁琐 开两个map 一个存城市 一个存名字

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<map>
using namespace std;
#define N 60010
#define LL long long
LL s[N<<];
LL a[N],pp[N];
map<string,int>q;
map<string,int>qq;
char pq[N][];
struct node
{
int d;
char s1[];
char s2[];
}bi[N];
struct mode
{
char ss[];
LL vv;
}ct[N];
int sd[N],g,gg,lo[N];
void up(int w)
{
s[w] = max(s[w<<],s[w<<|]);
}
void build(int l,int r,int w)
{
if(l==r)
{
s[w] = a[l];
return ;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
up(w);
}
void update(int p,LL d,int l,int r,int w)
{
if(l==r)
{
s[w]+=d;
return ;
}
int m = (l+r)>>;
if(p<=m)
update(p,d,l,m,w<<);
else
update(p,d,m+,r,w<<|);
up(w);
}
int query(int l,int r,int w)
{
if(l==r)
{
return l;
}
int m = (l+r)>>;
if(s[w<<]>s[w<<|])
return query(l,m,w<<);
else if(s[w<<]<s[w<<|])
return query(m+,r,w<<|);
else
return ;
}
bool cmp(mode a,mode b)
{
return strcmp(a.ss,b.ss)<;
}
int main()
{
int n,k,m,i;
char s1[],s2[];
LL p;
scanf("%d",&n);
for(i = ; i <= n ; i++)
{
scanf("%s%s %lld",s1,s2,&p);
if(!q[s2])
{
g++;
q[s2] = g;
a[q[s2]]+=p;
strcpy(pq[g],s2);
}
else
a[q[s2]]+=p;
if(!qq[s1])
{
gg++;
qq[s1] = gg;
pp[gg] = p;
}
lo[qq[s1]] = q[s2];
}
scanf("%d%d",&m,&k);
for(i = ; i <= k ; i++)
{
scanf("%d%s%s",&bi[i].d,bi[i].s1,bi[i].s2);
if(!q[bi[i].s2])
{
g++;
q[bi[i].s2] = g;
strcpy(pq[g],bi[i].s2);
}
}
build(,g,);
int o = query(,g,);
int t = ;
for(i = ; i <= k ; i++)
{
int o1 = qq[bi[i].s1];
int o2 = q[bi[i].s2];
int kk = bi[i].d;
if(o)
{
sd[o]+=(kk-t);
}
t = kk;
update(lo[o1],-pp[o1],,g,);
update(o2,pp[o1],,g,);
lo[o1] = o2;
o = query(,g,);
}
if(o)
sd[o] += m-t;
o = ;
for(i = ; i <= g ; i++)
{
if(sd[i])
{
strcpy(ct[o].ss,pq[i]);
ct[o].vv = sd[i];
o++;
}
}
sort(ct,ct+o,cmp);
for(i = ; i < o ; i++)
printf("%s %lld\n",ct[i].ss,ct[i].vv);
return ;
}