2018-2019 NEERC Southern Subregional C-Cloud Computing

問題のリンク

問題概要

1日につき $K$コアを必要としている。次の $ M $ 個の契約のうち任意の組合せを選択できる時、$N$日間における最小コストを求めよ。ただし、その日にレンタル可能なCPUが $K$コアに満たない場合、全てと契約するものとする。

• 契約毎に変数 $l,r,c,p$ が与えられる
• $l$日目から $r$日目にかけてCPUをレンタルできる
• 最大で $c$コアをレンタル可能で、1コア当たり $p$ のコストがかかる
• 1日毎に契約するコア数は変更可能である

制約

• $1 \leq N,K \leq 10^{6}$
• $1 \leq M \leq 2 \cdot 10^{5}$
• $1 \leq l \leq r \leq N$
• $1 \leq c,p \leq 10^{6}$

解法

イベントソート+セグ木(BIT)上の二分探索

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N=1<<20;
ll cnt[2*N+10],sum[2*N+10];

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,K,m; cin >> n >> K >> m;
    vector<vector<pair<int,int>>> query(N);
    for(int i=0;i<m;i++){
        int l,r,c,p; cin >> l >> r >> c >> p;
        query[l].push_back(make_pair(c,p));
        query[r+1].push_back(make_pair(-c,p));
    }
    auto update=[&](int x,int v)->void{
        ll c=(ll)x*(ll)v;
        for(x+=N;x>0;x>>=1){
            cnt[x]+=v; sum[x]+=c;
        }
    };
    ll res=0;
    for(int i=1;i<=n;i++){
        for(auto q:query[i]){
            update(q.second,q.first);
        }
        ll k=K;
        int u=1;
        while(u<N){
            if(k<=cnt[u*2])u=2*u;
            else{
                k-=cnt[2*u];
                res+=sum[2*u];
                u=u*2+1;
            }
        }
        res+=min(cnt[u],k)*(u-N);
    }
    printf("%lld\n",res);
}