Submission #1179938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179938		Szymon_Pilipczuk	Snowball (JOI21_ho_t2)	C++20	100 / 100	148 ms	12096 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define all(a) a.begin(),a.end()
#define ll long long
int main()
{
    int n,q;
    cin>>n>>q;
    vector<pair<ll,int>> x(n);
    for(int i = 0;i<n;i++)
    {
        x[i].nd = i;
        cin>>x[i].st;
    }
    sort(all(x));
    int m1[n];
    for(int i =0 ;i<n;i++)
    {
        m1[i] = x[i].nd;
    }
    vector<pair<ll,int>> g(n-1);
    for(int i = 0;i<n-1;i++)
    {
        g[i] = {x[i+1].st-x[i].st,i};
    }
    ll ans[n];
    for(int i = 0;i<n;i++) ans[i] = 0;
    sort(all(g));
    ll mn = 0;
    ll mx = 0;
    ll cu = 0;
    int j = 0;
    for(int i = 0;i<q;i++)
    {
        ll w;
        cin>>w;
        cu+=w;
        mn = min(mn,cu);
        mx = max(mx,cu);
        while(j < n-1&& mx - mn >= g[j].st)
        {
            if(cu > 0)
            {
                ans[g[j].nd+1]+= abs(mn);
                ans[g[j].nd]+= g[j].st-abs(mn);
            }
            else
            {
                ans[g[j].nd+1]+= g[j].st-mx;
                ans[g[j].nd]+= mx;
            }
            j++;
        }
    }
    while(j < n-1)
    {
        ans[g[j].nd+1] += abs(mn);
        ans[g[j].nd] += mx;
        j++;
    }
    ans[0] += abs(mn);
    ans[n-1]+= mx;
    vector<ll> tans(n);
    for(int i =0 ;i<n;i++)
    {
        tans[m1[i]] = ans[i];
    }
    for(int i = 0;i<n;i++)
    {
        cout<<tans[i]<<"\n";
    }
}

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