Submission #601513

#	Time	Username	Problem	Language	Result	Execution time	Memory
601513		pakhomovee	Snowball (JOI21_ho_t2)	C++17	100 / 100	99 ms	13752 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> x(n);
    for (int& i : x) {
        cin >> i;
    }
    vector<pair<int, int>> t;
    for (int i = 0; i + 1 < n; ++i) {
        t.push_back({x[i + 1] - x[i], i});
    }
    sort(t.begin(), t.end());
    int minDelta = 0, maxDelta = 0;
    int currDelta = 0;
    int ptr = 0;
    vector<int> res(n, 0);
    for (int i = 0; i < q; ++i) {
        int w;
        cin >> w;
        int prevMaxDelta = maxDelta;
        int prevMinDelta = minDelta;
        currDelta += w;
        minDelta = min(minDelta, currDelta);
        maxDelta = max(maxDelta, currDelta);
        while (ptr < t.size() && t[ptr].first <= maxDelta - minDelta) {
            if (prevMaxDelta == maxDelta) {
                res[t[ptr].second] += maxDelta;
                res[t[ptr].second + 1] += t[ptr].first - maxDelta;
            } else {
                res[t[ptr].second] += t[ptr].first - abs(minDelta);
                res[t[ptr].second + 1] += abs(minDelta);
            }
            ++ptr;
        }
    }
    for (int i = ptr; i < t.size(); ++i) {
        res[t[i].second] += maxDelta;
        res[t[i].second + 1] += abs(minDelta);
    }
    res[0] += abs(minDelta);
    res.back() += maxDelta;
    for (int i : res) {
        cout << i << ' ';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:36:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while (ptr < t.size() && t[ptr].first <= maxDelta - minDelta) {
      |                ~~~~^~~~~~~~~~
Main.cpp:32:13: warning: unused variable 'prevMinDelta' [-Wunused-variable]
   32 |         int prevMinDelta = minDelta;
      |             ^~~~~~~~~~~~
Main.cpp:47:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = ptr; i < t.size(); ++i) {
      |                       ~~^~~~~~~~~~

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