【題解】Codeforces 1406D. Three Sequences

【題目敘述】http://codeforces.com/contest/1406/problem/D

#include <iostream>
using namespace std;
 
long long n, q, first, a[100005], tot;
 
long long f(){
    long long l = -1e14, r = 1e14;
    while (r-l > 1){
        long long mid = (l+r)/2;
        if (a[0]-mid+tot <= mid) r = mid;
        else l = mid;
    }
    return r;
}
 
int main() {
    cin >> n;
    cin >> a[1];
    a[0] = a[1];
    for (int i = 2; i <= n; i++){
        cin >> a[i];
        a[i-1] = a[i]-a[i-1];
        if (a[i-1] > 0) tot += a[i-1];
    }
    cout << f() << "\n";
    cin >> q;
    for (int i = 0, l, r, x; i < q; i++){
        cin >> l >> r >> x;
        if (l == 1) a[0] += x;
        else{
            if (a[l-1] > 0) tot -= a[l-1];
            a[l-1] += x;
            if (a[l-1] > 0) tot += a[l-1];
        }
        if (r < n){
            if (a[r] > 0) tot -= a[r];
            a[r] -= x;
            if (a[r] > 0) tot += a[r];
        }
        cout << f() << "\n";
    }
}
分享本文 Share with friends