Submission #602214

#TimeUsernameProblemLanguageResultExecution timeMemory
602214gagik_2007Snowball (JOI21_ho_t2)C++17
33 / 100
2580 ms852 KiB
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

string findSum(string str1, string str2)
{
    if (str1.length() > str2.length())
        swap(str1, str2);
    string str = "";
    ll n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (ll i = 0; i < n1; i++)
    {
        ll sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    for (ll i = n1; i < n2; i++)
    {
        ll sum = ((str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    if (carry)
        str.push_back(carry + '0');
    reverse(str.begin(), str.end());
    return str;
}
bool isSmaller(string str1, string str2)
{
    ll n1 = str1.length(), n2 = str2.length();
    if (n1 < n2)
        return true;
    if (n2 < n1)
        return false;
    for (ll i = 0; i < n1; i++)
        if (str1[i] < str2[i])
            return true;
        else if (str1[i] > str2[i])
            return false;
    return false;
}
string findDiff(string str1, string str2)
{
    if (isSmaller(str1, str2))
        swap(str1, str2);
    string str = "";
    ll n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (ll i = 0; i < n2; i++) {
        ll sub
            = ((str1[i] - '0') - (str2[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    for (ll i = n2; i < n1; i++) {
        ll sub = ((str1[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    reverse(str.begin(), str.end());
    return str;
}

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;
ll a[1000007];
ll l[1000007];
ll r[1000007];
ll w[1000007];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        l[i] = a[i];
        r[i] = a[i];
    }
    for (int j = 0; j < k; j++) {
        ll x;
        cin >> x;
        if (x < 0) {
            x = abs(x);
            ll tmp = x - a[0] + l[0];
            w[0] += max(0ll, tmp);
            a[0] -= x;
            l[0] = min(l[0], a[0]);
            for (int i = 1; i < n; i++) {
                ll tmp = x - a[i] + l[i];
                w[i] += max(0ll, min(tmp, l[i] - r[i - 1]));
                a[i] -= x;
                l[i] = min(l[i], a[i]);
            }
        }
        else {
            ll tmp = x - r[0] + a[0];
            w[n - 1] += max(0ll, tmp);
            a[n - 1] += x;
            r[n - 1] = max(r[n - 1], a[n - 1]);
            for (int i = 0; i < n - 1; i++) {
                tmp = x - r[i] + a[i];
                w[i] += max(0ll, min(tmp, l[i + 1] - r[i]));
                a[i] += x;
                r[i] = max(r[i], a[i]);
            }
        }
        /*for (int i = 0; i < n; i++) {
            cout << i << ": " << l[i] << " " << r[i] << " " << a[i] << " " << w[i] << endl;
        }*/
    }
    for (int i = 0; i < n; i++) {
        cout << w[i] << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...