首页 > 代码库 > Money out of Thin Air
Money out of Thin Air
Money out of Thin Air
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Each employee of the company Oceanic Airlines, except for the director, has exactly one immediate superior. To encourage the best employees and best departments, the director can issue two kinds of orders:
- “employee x y z” — if the salary of employee x is less than y dollars, increase it by zdollars;
- “department x y z” — if the average salary in the department headed by employee x is less than y dollars, increase the salary of each employee at this department by z dollars (the department includes employee x and all her subordinates, not necessarily immediate).
Given the salaries of all the employees of Oceanic Airlines at the beginning of a year and all the salary increase orders issued by the director during the year, find the salaries of the employees by the end of the year. You may assume that the company didn‘t hire any new employees and didn‘t fire anyone during the year.
Input
The first line contains integers n, q, and s0, which are the number of employees at Oceanic Airlines, the number of salary increase orders, and the director‘s salary at the beginning of the year (1 ≤ n, q ≤ 50 000; 0 ≤ s0 ≤ 109). The employees are numbered from 0 to n − 1; the director‘s number is zero. In the ith of the following n − 1 lines you are given integers piand si, which are the number of the immediate superior and the salary at the beginning of the year of the employee with number i (0 ≤ pi ≤ i − 1; 0 ≤ si ≤ 109). The following q lines are the director‘s orders given chronologically. Each order has the form “employee x y z” or “department x y z” (the notation x, y, z is explained above), where 0 ≤ x ≤ n − 1 and 1 ≤ y, z ≤ 109.
Output
Output the salaries of all employees at Oceanic Airlines at the end of the year in the ascending order of the employees‘ numbers.
Sample
| input | output |
|---|---|
4 3 10 100 101 10employee 2 15 1employee 3 5 1department 0 10 1 | 2111211
|
分析：关键是对员工的原标号进行先序遍历后重新标号，这样每个员工所领导的部门就是一个连续的区间；
然后线段树进行区间修改，注意输出答案再把新标号代回原标号；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <hash_map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=1e5+10;const int dis[][2]={0,1,-1,0,0,-1,1,0};using namespace std;using namespace __gnu_cxx;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}int n,m,k,t,h[maxn],c[maxn],id[maxn],idx[maxn],tot,now,l[maxn],r[maxn];struct Node{ ll sum, lazy;} T[maxn<<2];void PushUp(int rt){ T[rt].sum = T[rt<<1].sum + T[rt<<1|1].sum;}void PushDown(int L, int R, int rt){ int mid = (L + R) >> 1; ll t = T[rt].lazy; T[rt<<1].sum += t * (mid - L + 1); T[rt<<1|1].sum += t * (R - mid); T[rt<<1].lazy += t; T[rt<<1|1].lazy += t; T[rt].lazy = 0;}void Build(int L, int R, int rt){ if(L == R) { T[rt].sum=c[idx[now++]]; return ; } int mid = (L + R) >> 1; Build(Lson); Build(Rson); PushUp(rt);}void Update(int l, int r, ll v, int L, int R, int rt){ if(l==L && r==R) { T[rt].lazy += v; T[rt].sum += v * (R - L + 1); return ; } int mid = (L + R) >> 1; if(T[rt].lazy) PushDown(L, R, rt); if(r <= mid) Update(l, r, v, Lson); else if(l > mid) Update(l, r, v, Rson); else { Update(l, mid, v, Lson); Update(mid+1, r, v, Rson); } PushUp(rt);}ll Query(int l, int r, int L, int R, int rt){ if(l==L && r== R) { return T[rt].sum; } int mid = (L + R) >> 1; if(T[rt].lazy) PushDown(L, R, rt); if(r <= mid) return Query(l, r, Lson); else if(l > mid) return Query(l, r, Rson); return Query(l, mid, Lson) + Query(mid + 1, r, Rson);}struct node1{ int to,nxt;}p[maxn];struct node2{ char p[10]; int x,y,z;}q[maxn];void add(int x,int y){ tot++; p[tot].to=y; p[tot].nxt=h[x]; h[x]=tot;}void dfs(int u){ id[u]=++now; idx[now]=u; l[u]=now; for(int i=h[u];i;i=p[i].nxt) { dfs(p[i].to); } r[u]=now; return;}int main(){ int i,j; scanf("%d%d%d",&n,&m,&c[1]); rep(i,2,n) { int a,b; scanf("%d%d",&a,&b); a++; add(a,i); c[i]=b; } rep(i,1,m)scanf("%s%d%d%d",q[i].p,&q[i].x,&q[i].y,&q[i].z),q[i].x++; dfs(1); now=1; Build(1,n,1); rep(i,1,m) { if(q[i].p[0]==‘e‘) { if(Query(id[q[i].x],id[q[i].x],1,n,1)<q[i].y) Update(id[q[i].x],id[q[i].x],q[i].z,1,n,1); } else { if((double)Query(l[q[i].x],r[q[i].x],1,n,1)/(r[q[i].x]-l[q[i].x]+1)<q[i].y) Update(l[q[i].x],r[q[i].x],q[i].z,1,n,1); } } rep(i,1,n)printf("%lld\n",Query(id[i],id[i],1,n,1)); //system("Pause"); return 0;}
Money out of Thin Air
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。