Codeforces 1070C Cloud Computing

Cloud Computing
(http://codeforces.com/problemset/problem/1070/C)

\(1\sim n\)번 칸에서 각각 최대 \(k\)개의 코어를 사야 하는데,
당연히 살 수 있는 코어 중에서 가격이 싼 것 부터 차례대로 사는게 이득이다.

그렇다고 계획들을 정렬한 뒤 싼 것부터 하나하나 추가해가다보면, 어떤 칸에서 코어를 \(k\)개 넘게 샀는지를 확인하기 힘들다.
그래서 계획별로 보지 않고, 칸 별로 어떤 계획을 사용할지를 확인해야한다.

현재 \(i\)번째 칸에서 적용할 계획을 확인하고 있다면, 구간에 \(i\)가 포함되는 계획들을 찾아야 한다.
어차피 \(1\)번째 칸부터 \(n\)번째 칸까지 차례대로 볼 것이므로,
\(i\)가 계획의 시작점일 때 계획 후보에 넣고, 끝점일 때 빼면 된다.
구체적으로, 적용되는 구간이 \(l\)부터 \(r\)까지인 계획은 \(l\)번째 칸에 계획을 넣도록 체크해두고, \(r\)번째 칸에 계획을 빼도록 체크해둔 뒤 \(i\)번째 칸에서는 \(i\)번째 칸에서 넣을 계획은 넣고 뺄 계획은 빼면 된다.

이제 \(i\)번째 칸에서 사용할 수 있는 계획들은 찾았으니, 어떤 계획을 사용할지를 정해야한다.
다르게 생각하면 '얼마짜리 코어 까지 사야지 \(k\)개를 채울 수 있을까?'를 묻는 것인데,
이 질문을 이분탐색으로 찾을 수 있다.

현재 사용할수 있는 계획의 코어 가격이 \(p\)고 개수가 \(c\)면 배열의 \(p\)번째 칸에 \(c\)개를 더해둔다.
그러면 배열에서 \(1\sim t\)까지 원소의 합이 \(k\)를 넘을 때 \(t\)의 최솟값이 위 질문의 답이다.
써야하는 돈도 마찬가지로 배열을 만들어 \(1\sim t\)까지이니 그만큼 답에 더해주면 된다.
구간합도 펜윅트리, 세그먼트트리를 쓰면 \(\log\)시간 안에 구할 수 있으니 총 \(O(n\log^2{p})\)만에 답을 찾을 수 있다.

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 62 63 64

#include <bits/stdc++.h>   using namespace std;   vector<pair<long long, long long> > u[1000001], v[1000001]; pair<long long, long long> tree[1000002];   int main() {     int n, k, m;     scanf("%d %d %d", &n, &k, &m);     for (int i = 0;i < m;++i) {         int l, r;         long long c, p;         scanf("%d %d %lld %lld", &l, &r, &c, &p);         u[l].push_back({ c, p });         v[r].push_back({ c, p });     }       long long ans = 0;     for (int i = 1;i <= n;++i) {         for (pair<long long, long long> now : u[i])             for (int x = now.second;x <= 1000001;x += x & -x) {                 tree[x].first += now.first;                 tree[x].second += now.first * now.second;             }           long long low = 1, high = 1000000, ov = 1000001;         while (low <= high) {             long long mid = (low + high) / 2;               pair<long long, long long> sum = { 0, 0 };             for (int x = mid;x > 0;x -= x & -x) {                 sum.first += tree[x].first;                 sum.second += tree[x].second;             }               if (sum.first >= k) {                 ov = min(ov, mid);                 high = mid - 1;             }             else                 low = mid + 1;         }           long long tot = 0;         for (int x = ov;x > 0;x -= x & -x) {             tot += tree[x].first;             ans += tree[x].second;         }           if (tot > k)             ans -= ov * (tot - k);           for (pair<long long, long long> now : v[i])             for (int x = now.second; x <= 1000001;x += x & -x) {                 tree[x].first -= now.first;                 tree[x].second -= now.first * now.second;             }     }       printf("%lld", ans);       return 0; } Colored by Color Scripter

cs