Submission #1125565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125565		AverageAmogusEnjoyer	Snowball (JOI21_ho_t2)	C++20	100 / 100	77 ms	11336 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}
const int N=200200;
ll a[N];
int n,q;
ll prefMax[N],prefMin[N];
ll sum[N];
ll ans[N];
ll pref[N];

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i=1;i<=n;i++)
        cin >> a[i];
    for (int i=1;i<=q;i++) {
        ll x;
        cin >> x;
        pref[i]=pref[i-1]+x;
        prefMax[i]=max(prefMax[i-1],pref[i]);
        prefMin[i]=min(prefMin[i-1],pref[i]);
        sum[i]=prefMax[i]-prefMin[i];
    }
    for (int i=1;i+1<=n;i++) {
        int lo=0,hi=q;
        while(lo<hi) {
            int mid=lo+(hi-lo+1)/2;
            if (sum[mid]<=a[i+1]-a[i])
                lo=mid;
            else    
                hi=mid-1;
        }
        ll r=0;
        r+=prefMax[lo];
            // cout << lo << endl;
        if (lo + 1 <= q) {
            // cout << (pref[lo+1] < a[i+1]-a[i]+prefMin[lo] ? 1 : 0) << endl;
            r+=max(0LL,min(pref[lo+1],a[i+1]-a[i]+prefMin[lo])-prefMax[lo]);
        }
        ans[i+1]=min(-(lo + 1 <= q ? prefMin[lo+1]:prefMin[lo]),a[i+1]-a[i]-r);
        ans[i]+=r;
        // cout << ans[i] << " " << ans[i + 1] << endl;
    }
    ans[1]+=-prefMin[q];
    ans[n]+=prefMax[q];
    for (int i=1;i<=n;i++)
        cout << ans[i] << "\n";
}

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