题目描述
虱子国王尼特这天有点不舒服,它周围的 个医生立刻开出了药方:第 个医生告诉它,从这天起的第 天到第 天,它应该服用 这 种药,每天每种药应当服用恰好一片。注意,如果有多个医生的药方里都要求尼特在第 天服用第 种药,那尼特在第 p 天仍然只会服用一片第 种药。编号为 的药每片需要 元钱。
然而,由于尼特的疏忽,有恰好一位庸医混进了医生队伍里,但尼特并不知道哪位医生是庸医。所以它想知道,对于所有 ,如果它按照除了第 个医生之外的所有医生的药方吃药,它总共将花费多少钱。
输入格式
第一行两个正整数 ,,分别为医生数和药片种类数。
接下来一行 个正整数 。
接下来 行,第 行描述第 个医生。首先三个正整数 ,,,后面 个正整数 。保证 互不相同。
输出格式
输出 个非负整数,第 个表示,如果尼特认为第 个医生是庸医并除开他的药方,它总共将花费多少钱。
样例输入输出
样例输入 1 2 3 4 5 6 7
| 5 4 10000 1000 100 10 3 4 2 2 3 4 8 3 1 2 4 6 7 2 3 4 8 9 2 1 4 2 6 3 1 2 3
|
样例输出 1
| 87660 75640 87560 77650 66460
|
样例解释 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| 这里仅解释输出中的第一个和第五个数。
如果第一位医生是庸医,则尼特:
在第 2,3 天会吃药片 1,2,3。花费 11100×2=22200 元。 在第 4,5,6,7 天会吃药片 1,2,3,4。花费 11110×4=44440 元。 在第 8 天会吃药片 1,2,4。花费 11010 元。 在第 9 天会吃药片 1,4。花费 10010 元。 总花费 87660 元。
如果第五位医生是庸医,则尼特:
在第 3 天会吃药片 2,3。花费 1100 元。 在第 4 天会吃药片 1,2,3,4。花费 11110 元。 在第 5 天会吃药片 1,2,4。花费 11010 元。 在第 6,7 天会吃药片 1,2,3,4。花费 11110×2=22220 元。 在第 8 天会吃药片 1,2,4。花费 11010 元。 在第 9 天会吃药片 1,4。花费 10010 元。 总花费 66460 元。
|
数据范围
题解
定义第 个医生的贡献值为: 其中定义为第个医生的药方中有第 种药片在第 天无其它医生开该药。,
详细见代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| #include <iostream> #include <algorithm> #include <cstdio> #include <vector> #define int long long using namespace std; int n ,m; int c[500005]; int l[500005] ,r[500005]; int l2[500005] ,r2[500005]; vector<int> x[500005]; int a[1000005] ,ans[500005] ,sum; int cnt[1000005] ,cur[1000005]; int wh(int x ,int len){ return lower_bound(a+1 ,a+len+1 ,x)-a; } main() { cin >> n >> m; for(int i=1;i<=m;i++) cin >> c[i]; for(int i=1;i<=n;i++){ int k ,a; cin >> l[i] >> r[i] >> k; for(int j=1;j<=k;j++){ cin >> a; x[a].push_back(i); } } for(int i=1;i<=m;i++){ if(x[i].size()==0)continue; int len=0; for(int j=0;j<x[i].size();j++) a[++len]=l[x[i][j]] ,a[++len]=r[x[i][j]]+1; sort(a+1 ,a+len+1); len=unique(a+1 ,a+len+1)-a-1; for(int j=0;j<x[i].size();j++){ int w=x[i][j]; l2[w]=wh(l[w] ,len) ,r2[w]=wh(r[w]+1 ,len)-1; } for(int j=0;j<x[i].size();j++){ int w=x[i][j]; cnt[l2[w]]++ ,cnt[r2[w]+1]--; cur[l2[w]]^=w ,cur[r2[w]+1]^=w; } for(int j=1;j<=len;j++) cnt[j]+=cnt[j-1] ,cur[j]^=cur[j-1]; for(int j=1;j<=len;j++){ if(cnt[j]) sum+=c[i]*(a[j+1]-a[j]); if(cnt[j]==1) ans[cur[j]]+=c[i]*(a[j+1]-a[j]); cnt[j]=cur[j]=0; } } for(int i=1;i<=n;i++) cout << sum-ans[i] << ' '; }
|