oj.uz

Submission #602197

# Submission time Handle Problem Language Result Execution time Memory
602197 2022-07-22T17:03:11 Z SamAnd Snowball (JOI21_ho_t2) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int n, q;
ll x[N];
ll w[N];

ll p[N];
ll maxu[N], minu[N];

void solv()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> x[i];
    for (int i = 1; i <= q; ++i)
        cin >> w[i];

    for (int i = 1; i <= q; ++i)
        p[i] = p[i - 1] + w[i];
    for (int i = 1; i <= n; ++i)
    {
        minu[i] = min(minu[i - 1], p[i]);
        maxu[i] = max(maxu[i - 1], p[i]);
    }

    for (int i = 1; i <= n; ++i)
    {
        ll ans = 0;
        if (i == 1)
        {
            ans -= minu[q];
        }
        else
        {
            int l = 1, r = q;
            int u = 0;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if (maxu[m] - minu[m] <= x[i] - x[i - 1])
                {
                    u = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }

            int m = u;
            if (m == q || p[m + 1] > 0)
            {
                ans -= minu[m];
            }
            else
            {
                ans += (x[i] - x[i - 1] - maxu[m]);
            }
        }

        if (i == n)
        {
            ans += maxu[q];
        }
        else
        {
            int l = 1, r = q;
            int u = 0;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if (maxu[m] - minu[m] <= x[i + 1] - x[i])
                {
                    u = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }

            int m = u;
            if (m == q || p[m + 1] < 0)
            {
                ans += maxu[m];
            }
            else
            {
                ans += (x[i + 1] - x[i] + minu[m]);
            }
        }
        cout << ans << "\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -