Submission #940563

#	Time	Username	Problem	Language	Result	Execution time	Memory
940563		Hanksburger	Snowball (JOI21_ho_t2)	C++17	100 / 100	95 ms	17188 KiB

Main

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, pair<long long, long long> > > v;
pair<long long, long long> p[200005];
long long a[200005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, x, sum=0, mx0=0, mx1=0;
    cin >> n >> m;
    a[0]=-1e18, a[n+1]=1e18;
    for (long long i=1; i<=n; i++)
        cin >> a[i];
    v.push_back({0, {0, 0}});
    for (long long i=1; i<=m; i++)
    {
        cin >> x;
        sum+=x;
        mx0=max(mx0, sum);
        mx1=max(mx1, -sum);
        v.push_back({mx0+mx1, {mx0, mx1}});
    }
    for (long long i=0; i<=n; i++)
    {
        long long ind=lower_bound(v.begin(), v.end(), make_pair(a[i+1]-a[i]+1, make_pair(0LL, 0LL)))-v.begin();
        if (ind==m+1)
            p[i]=v[ind-1].second;
        else if (v[ind-1].second.first==v[ind].second.first)
            p[i]={v[ind].second.first, a[i+1]-a[i]-v[ind].second.first};
        else
            p[i]={a[i+1]-a[i]-v[ind].second.second, v[ind].second.second};
        if (i)
            cout << p[i-1].second+p[i].first << '\n';
    }
}

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