阅读背景:

CF1070 C. Cloud Computing (线段树)

来源:互联网 

Buber is a Berland technology company that specializes in waste of investor's money. Recently Buber decided to transfer its infrastructure to a cloud. The company decided to rent CPU cores in the cloud for n">nn consecutive days, which are numbered from 1">11 to n">nn . Buber requires k">kk CPU cores each day.

The cloud provider offers m">mm tariff plans, the i">ii -th tariff plan is characterized by the following parameters:

li">lili and ri">riri — the i">ii-th tariff plan is available only on days from li">lili to ri">riri, inclusiv

ci">cici — the number of cores per day available for rent on the i">ii-th tariff plan,

pi">pipi — the price of renting one core per day on the i">ii-th tariff plan. 

Buber can arbitrarily share its computing core needs between the tariff plans. Every day Buber can rent an arbitrary number of cores (from 0 to ci">cici ) on each of the available plans. The number of rented cores on a tariff plan can vary arbitrarily from day to day.

Find the minimum amount of money that Buber will pay for its work for n">nn days from 1">11 to n">nn . If on a day the total number of cores for all available tariff plans is strictly less than k">kk , then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly k">kk cores this day.

Input

The first line of the input contains three integers n">nn , k">kk and m">mm (1≤n,k≤106,1≤m≤2⋅105">1n,k106,1m21051≤n,k≤106,1≤m≤2⋅105 ) — the number of days to analyze, the desired daily number of cores, the number of tariff plans.

The following m">mm lines contain descriptions of tariff plans, one description per line. Each line contains four integers li">lili , ri">riri , ci">cici , pi">pipi (1≤li≤ri≤n">1lirin1≤li≤ri≤n , 1≤ci,pi≤106">1ci,pi1061≤ci,pi≤106 ), where li">lili and ri">riri are starting and finishing days of the i">ii -th tariff plan, ci">cici — number of cores, pi">pipi — price of a single core for daily rent on the i">ii -th tariff plan.

Output

Print a single integer number — the minimal amount of money that Buber will pay.

Examples
Input
Copy
5 7 3
1 4 5 3
1 3 5 2
2 5 10 1
Output
Copy
44
Input
Copy
7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8
Output
Copy
462
Input
Copy
4 100 3
3 3 2 5
1 1 3 2
2 4 4 4
Output
Copy
64




首先贪心的想就是无论如何都要先选便宜的,会想到先排序,
然后给的区间有点区间覆盖的意思,也就是往线段树那边去想了,然后发现对一个区间进行覆盖之后,不好从某一个点里取出最小的k个
所以就尬住了qwq
然后题解是用了扫面线的思想,到了第i天,对当前可用的plan建立线段树,那k去线段树上找前k个,这样思路瞬间就清晰了




 1 #include"bits/stdc++.h"  2 using namespace std;  3 #define int long long  4 #define IO ios::sync_with_stdio(0);  5 vector<int > add[2000000],del[2000000];  6  7 struct pp  8 {  9 int size,v; 10 }tr[4000000]; 11 12 struct aa 13 { 14 int l,r,c,p; 15 bool operator<(const aa b)const 16  { 17 return c<b.c; 18  } 19 }edge[300000]; 20 int n,m,k; 21 22 void upd(int rt,int l,int r,int pos,int c) 23 { 24 if(l==r) 25  { 26 tr[rt].size += c; 27 tr[rt].v += pos*c; 28 return ; 29 }int mid = l+r>>1; 30 if(pos<=mid)upd(rt<<1,l,mid,pos,c); else upd(rt<<1|1,mid+1,r,pos,c); 31 32 tr[rt].size = tr[rt<<1].size + tr[rt<<1|1].size; 33 tr[rt].v = tr[rt<<1].v + tr[rt<<1|1].v; 34 35 } 36 37 int que(int rt,int l,int r,int k) 38 { 39 if(l==r) 40  { 41 return min(tr[rt].size,k)*l; 42  } 43 int mid=l+r>>1; 44 if(k<=tr[rt<<1].size)return que(rt<<1,l,mid,k); 45 else return tr[rt<<1].v + que(rt<<1|1,mid+1,r,k-tr[rt<<1].size); 46 } 47 48 signed main() 49 { 50  IO 51 cin>>n>>k>>m; int maxn=1000; 52 for(int i=1;i<=m;++i) 53  { 54 cin>>edge[i].l>>edge[i].r>>edge[i].c>>edge[i].p; 55 add[edge[i].l].push_back(i); maxn=max(maxn,edge[i].p); 56  del[edge[i].r].push_back(i); 57  } 58 int ans=0; 59 for (int i=1;i<=n;i++) 60  { 61 62 for(auto j:add[i])upd(1,1,maxn,edge[j].p,edge[j].c); 63 64 ans += que(1,1,maxn,k); 65 for (auto j:del[i])upd(1,1,maxn,edge[j].p,-edge[j].c); 66 67  } 68 cout<<ans; 69 70 71 72 }

 


分享到: