Submission #763795

#	Time	Username	Problem	Language	Result	Execution time	Memory
763795		sheldon	Snowball (JOI21_ho_t2)	C++14	100 / 100	77 ms	18916 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long

void solve() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<array<long long, 3>> v;
    vector<int> ans(n);
    for (int i = 0; i + 1 < n; ++i) {
        v.push_back({abs(a[i] - a[i + 1]), 1LL * i, 1LL * i + 1});
    }
    sort(v.begin(), v.end());
    long long l = 0, r = 0, delta = 0;
    long long A, B;
    vector<long long> deltas;
    for (int i = 0; i < q; ++i) {
        long long x;
        cin >> x;
        delta += x;
        if (delta < l || delta > r) {
            deltas.push_back(delta);
        }
        l = min(delta, l);
        r = max(delta, r);
    }
    if (n == 1) {
        cout << l + r << '\n';
        return;
    }
    A = l, B = r;
    l = 0, r = 0;
    int idx = 0;
    for (int i = 0; i < v.size(); ++i) {
        while (idx < deltas.size() && a[v[i][1]] + r < a[v[i][2]] + l) {
            l = min(l, deltas[idx]);
            r = max(r, deltas[idx]);
            ++idx;
        }
        if (a[v[i][1]] + r > a[v[i][2]] + l) {
            if (deltas[idx - 1] < 0) {
                ans[v[i][1]] += r;
                ans[v[i][2]] += v[i][0] - r;
            } else {
                ans[v[i][2]] += abs(l);
                ans[v[i][1]] += v[i][0] - abs(l);
            }
        }  else {
            ans[v[i][2]] += abs(l);
            ans[v[i][1]] += r;
        }
   }
   ans[0] += abs(A);
   ans[n - 1] += B;
   for (long long x : ans) {
        cout << x << '\n';
   }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~
Main.cpp:40:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while (idx < deltas.size() && a[v[i][1]] + r < a[v[i][2]] + l) {
      |                ~~~~^~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67