Cloud Computing CodeForces - 1070C(가중치 세그먼트 트리)
The cloud provider offers m tariff plans, the i-th tariff plan is characterized by the following parameters:
li and ri — the i-th tariff plan is available only on days from li to ri, inclusive, ci — the number of cores per day available for rent on the i-th tariff plan, pi — the price of renting one core per day on the i-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) 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 days from 1 to n. If on a day the total number of cores for all available tariff plans is strictly less than k, then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly k cores this day.
Input The first line of the input contains three integers n, k and m (1≤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 lines contain descriptions of tariff plans, one description per line. Each line contains four integers li, ri, ci, pi (1≤li≤ri≤n, 1≤ci,pi≤106), where li and ri are starting and finishing days of the i-th tariff plan, ci — number of cores, pi — price of a single core for daily rent on the i-th tariff plan.
Output Print a single integer number — the minimal amount of money that Buber will pay.
Examples Input 5 7 3 1 4 5 3 1 5 2 5 2 5 10 1 Output 44 Input 7 13 5 2 3 10 7 3 5 10 10 1 2 10 1 2 10 6 6 4 5 10 9 3 4 10 8 Output 462 Input 4 100 3 3 3 2 5 1 3 2 2 1 3 2 2 2 2 2 4 Output 64 이벤트는 총 n 일 동안 총 m 개의 물품을 각 물품 은 리 부터 리 까지 총 c 건 으로 한 건당 가격 p 다.매일 k종의 물품이 필요하며, k개의 물품이 부족하면 그럭저럭 살아서 사용한다.최소 비용은 얼마냐고 물었다.우리는 가치에 따라 권치선 트리에 어떤 물품이 공급될 때 권치선 트리를 직접 삽입하고 물품이 공급되지 않을 때 권치선 트리에서 이 물품을 삭제한다.코드는 다음과 같습니다.
#include
#define ll long long
using namespace std;
const int maxx=1e6+100;
vector > in[maxx],out[maxx];
struct node{
int l;
int r;
ll sum;
ll num;
}p[maxx<<2];
int n,m,k;
void init()
{
for(int i=0;i<=n;i++)
{
in[i].clear();
out[i].clear();
}
}
inline void pushup(int cur)
{
p[cur].num=p[cur<<1].num+p[cur<<1|1].num;
p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum;
}
inline void build(int l,int r,int cur)
{
p[cur].l=l;
p[cur].r=r;
p[cur].num=0;
p[cur].sum=0;
if(l==r) return ;
int mid=l+r>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
}
inline void update(int num,int pos,int cur)
{
int L=p[cur].l;
int R=p[cur].r;
if(L==R)
{
p[cur].num+=num;
p[cur].sum+=(ll)num*(ll)L;
return ;
}
int mid=L+R>>1;
if(pos<=mid) update(num,pos,cur<<1);
else update(num,pos,cur<<1|1);
pushup(cur);
}
inline ll query(int num,int cur)
{
int L=p[cur].l;
int R=p[cur].r;
if(L==R) return (ll)L*min(p[cur].num,(ll)num);
if(num<=p[cur<<1].num) return query(num,cur<<1);
else return (p[cur<<1].sum+query(num-p[cur<<1].num,cur<<1|1));
}
int main()
{
int l,r,x,y;
while(~scanf("%d%d%d",&n,&k,&m))
{
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&l,&r,&x,&y);
in[l].push_back(make_pair(x,y));
out[r].push_back(make_pair(x,y));
}
ll ans=0;
build(1,maxx,1);
for(int i=1;i<=n;i++)
{
for(int j=0;j
열심히 힘내라 a야,(o)/~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.