Submission #1168554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168554		altern23	Snowball (JOI21_ho_t2)	C++20	100 / 100	411 ms	9884 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, q; cin >> n >> q;
        vector<ll> a(n + 5), w(q + 5), pmx(q + 5), pmn(q + 5);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }

        ll sum = 0;
        for(int i = 1; i <= q; i++){
            cin >> w[i];
            sum += w[i];
            pmx[i] = max(pmx[i - 1], sum);
            pmn[i] = min(pmn[i - 1], sum);
        }

        vector<ll> ans(n + 5);
        for(int i = 1; i <= n; i++){
            if(i == 1){
                ans[i] += abs(pmn[q]);
            }
            else{
                ll res = a[i] - a[i - 1];
                ll lf = 0, rg = res, dist = 0;
                for(;lf <= rg;){
                    ll mid = (lf + rg) / 2;
                    ll x = lower_bound(pmx.begin() + 1, pmx.begin() + 1 + q, mid) - pmx.begin();
                    if(x != q + 1 && a[i] + pmn[x] >= a[i - 1] + mid){
                        dist = mid;
                        lf = mid + 1;
                    }
                    else rg = mid - 1;
                }
                ans[i - 1] += dist;
                ans[i] += min(abs(pmn[q]), a[i] - a[i - 1] - dist);
            }
            if(i == n) ans[i] += pmx[q];
        }

        for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
    }   
}

/*

*/ 

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