Submission #529538

#	Time	Username	Problem	Language	Result	Execution time	Memory
529538		syl123456	Snowball (JOI21_ho_t2)	C++17	100 / 100	811 ms	13004 KiB

Main

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
    i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << " :";
    for (T _i : j)
        i << ' ' << _i;
    i << '}';
}

typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

typedef pair<ll, int> pl;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    ll a[n], b[q];
    for (ll &i : a)
        cin >> i;
    for (ll &i : b)
        cin >> i;
    for (int i = 1; i < q; ++i)
        b[i] += b[i - 1];
    vector<pl> vl, vr;
    vl.emplace_back(0, 0), vr.emplace_back(0, 0);
    for (int i = 0; i < q; ++i) {
        if (b[i] < 0)
            vl.emplace_back(-b[i], i);
        else if (b[i] > 0)
            vr.emplace_back(b[i], i);
    }
    sort(all(vl)), sort(all(vr));
    vector<pl> tmp;
    for (auto [i, j] : vl) {
        while (!tmp.empty() && tmp.back().second >= j)
            tmp.pop_back();
        tmp.emplace_back(i, j);
    }
    vl = tmp, tmp.clear();
    for (auto [i, j] : vr) {
        while (!tmp.empty() && tmp.back().second >= j)
            tmp.pop_back();
        if (tmp.empty() || tmp.back().first < i)
            tmp.emplace_back(i, j);
    }
    vr = tmp;
    ll ans[n]{}, mxl = vl.back().first, mxr = vr.back().first;
    ans[0] += mxl, ans[n - 1] += mxr;
    for (int i = 0; i < n - 1; ++i) {
        if (a[i + 1] - a[i] >= mxl + mxr) {
            ans[i] += mxr, ans[i + 1] += mxl;
            continue;
        }
        ll len = a[i + 1] - a[i];
        ll l = max(0ll, len - mxl), r = min(len, mxr) + 1;
        while (l < r - 1) {
            ll mid = l + r >> 1;
            if (lower_bound(all(vr), pl(mid, -1))->second < lower_bound(all(vl), pl(len - mid + 1, -1))->second)
                l = mid;
            else
                r = mid;
        }
        ans[i] += l, ans[i + 1] += len - l;
    }
    for (ll i : ans)
        cout << i << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | }
      | ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:83:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             ll mid = l + r >> 1;
      |                      ~~^~~

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