Submission #1070890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070890		dpsaveslives	Snowball (JOI21_ho_t2)	C++17	100 / 100	97 ms	15420 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5+10;
ll A[MAXN],W[MAXN],ans[MAXN],minp[MAXN],maxp[MAXN];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,Q; cin >> N >> Q;
    ll psum = 0ll;
    for(int i = 1;i<=N;++i){
        cin >> A[i];
    }
    for(int i = 1;i<=Q;++i){
        cin >> W[i];
        psum += W[i];
        minp[i] = max(minp[i-1],-psum);
        maxp[i] = max(maxp[i-1],psum);
    }
    ans[1] += minp[Q]; ans[N] += maxp[Q];
    for(int i = 1;i<=N-1;++i){
        if(A[i+1]-A[i] >= maxp[Q]+minp[Q]){
            ans[i] += maxp[Q];
            ans[i+1] += minp[Q];
        }
        else{
            int lo = 1, hi = Q+1;
            while(lo < hi){
                int mid = lo+(hi-lo)/2;
                if(A[i+1]-A[i] < maxp[mid]+minp[mid]){
                    hi = mid;
                }
                else{
                    lo = mid+1;
                }
            }
            if(minp[lo] == minp[lo-1]){
                ans[i+1] += minp[lo];
                ans[i] += A[i+1]-A[i]-minp[lo];
            }
            else{
                ans[i+1] += A[i+1]-A[i]-maxp[lo];
                ans[i] += maxp[lo];
            }
        }
    }
    for(int i = 1;i<=N;++i){
        cout << ans[i] << "\n";
    }
    return 0;
}

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