제출 #1186621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186621		user736482	Snowball (JOI21_ho_t2)	C++20	100 / 100	57 ms	13096 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll a,b,c,d,t,n,m,ans[1000007],l,q;
vector<ll>x,w={0};
vector<pair<ll,pair<ll,ll>>>s;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(ll i=0;i<n;i++){
        cin>>a;
        x.pb(a);
    }
    for(ll i=0;i<q;i++){
        cin>>a;
        w.pb(w.back()+a);
    }
    s.pb({INFL,{(n-1),0}});
    for(ll i=1;i<n;i++){
        s.pb({x[i]-x[i-1],{i-1,(i)}});
    }
    sort(s.begin(),s.end());
    reverse(s.begin(),s.end());
    a=0;
    b=0;
    for(ll i=0;i<q;i++){
        a=min(a,w[i+1]);
        b=max(b,w[i+1]);
        while(s.size() && -a+b>=(s.back()).ff){
            auto pom=(s.back());
            if(w[i+1]>0){
                ans[pom.ss.ss]-=a;
                ans[pom.ss.ff]+=pom.ff+a;
            }
            else{
                ans[pom.ss.ff]+=b;
                ans[pom.ss.ss]+=(pom.ff-b);
            }
            s.pop_back();
        }
    }
    while(s.size()){
        auto pom=s.back();
        ans[pom.ss.ff]+=b;
        ans[pom.ss.ss]-=a;
        s.pop_back();
    }
    for(ll i=0;i<n;i++)cout<<ans[i]<<"\n";
    return 0;
}

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