[Algorithm Elementary][NOIP2012]借教室

Thinking Process

Use binary search and testify every value.
Assume you have known answer and check answer wheather right. If not right, how to update answer and testify it again until you verify its correctness.
This is the process of this excersize.
We can use difference to transfer interval update to point update in testify code. And finally sum them up. If one value in process less than zero return false.

Code

#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;

struct ty{
    ll d, s, j;    
}a[1000010];
ll b[1000010];
ll diff[1000010];
ll n, m;
bool check(ll x) {
    memset(diff, 0, sizeof(diff));
    for(ll i = 1;  i <= n; i ++) diff[i] = b[i] - b[i - 1];
    for(ll i = 1;  i <= x;i ++) {
        diff[a[i].s] -= a[i].d;
        diff[a[i].j + 1] += a[i].d;
    } 
    ll res = 0;
    for(ll i = 1; i <= n; i ++){
        res += diff[i];
        if(res < 0) return false;
    }
    return true;
} 
int main() {
    cin >> n >> m;
    for(ll i = 1; i <= n ; i++ ) cin >> b[i];
    for(ll i = 1; i <= m ; i ++) {
        cin >> a[i].d >> a[i].s >> a[i].j;
    }
    ll l = 1, r = 1e6 + 10;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    } 
    
    if(check(l)) cout << 0 << endl;
    else {
        cout << "-1" << endl << l;
    }
}