【題解】AtCoder ABC 183D – Water Heater

【題目敘述】https://atcoder.jp/contests/abc183/tasks/abc183_d
【解題想法】前綴和

#include <bits/stdc++.h>
using namespace std;

long long n, w, bit[200005];

void update(int x, long long u){
    while (x <= 200000){
        bit[x] += u;
        x += x & (-x);
    }
}
long long query(int x){
    long long ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}

int main(){
    cin >> n >> w;
    long long s, t, p;
    for (int i = 0; i < n; i++){
        cin >> s >> t >> p;
        update(s+1, p);
        update(t+1, -p);
    }
    for (int i = 1; i <= 200000; i++){
        if (query(i) > w){
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}

分享本文 Share with friends