Submission #488560

#	Time	Username	Problem	Language	Result	Execution time	Memory
488560		Lobo	Snowball (JOI21_ho_t2)	C++17	100 / 100	481 ms	16896 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220000

ii n, m;
ll w[maxn], ps[maxn], x[maxn], mx[maxn], mn[maxn], ans[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> m;

    for(ii i = 1; i <= n; i++) {
        cin >> x[i];
    }

    for(ii i = 1; i <= m; i++) {
        cin >> w[i];
        ps[i] = ps[i-1] + w[i];
        mn[i] = min(mn[i-1],ps[i]);
        mx[i] = max(mx[i-1],ps[i]);
    }

    ans[1]+= abs(mn[m]);
    ans[n]+= mx[m];

    for(ii i = 1; i < n; i++) {
        ll d = x[i+1]-x[i];
        if(mx[m] <= d+mn[m]) {
            ans[i]+= mx[m];
            ans[i+1]+= abs(mn[m]);
            continue;
        }


        ll l1 = 0;
        ll r1 = d;
        ll ans1 = 0;
        while(l1 <= r1) {
            ll mid1 = (l1+r1)/2;

            ll l2 = 0;
            ll r2 = m;
            ll ans2 = -1;
            while(l2 <= r2) {
                ll mid2 = (l2+r2)/2;
            
                if(mx[mid2] >= mid1) {
                    ans2 = mid2;
                    r2 = mid2-1;
                }
                else {
                    l2 = mid2+1;
                }
            }

            // cout << d << " " << mid1 << " " << ans2 << " " << endl;

            if(ans2 != -1 && d+mn[ans2] >= mid1) {
                ans1 = mid1;
                l1 = mid1+1;
            }
            else {
                r1 = mid1-1;
            }
        }

        // cout << " " << d << " " << ans1 << endl;

        ans[i]+= ans1;
        ans[i+1]+= d-ans1;
    }

    for(ii i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
}

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