Submission #702190

#	Time	Username	Problem	Language	Result	Execution time	Memory
702190		nicky4321	Snowball (JOI21_ho_t2)	C++14	100 / 100	93 ms	13728 KiB

Main

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define vi vector<int>
#define vl vector<ll>
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
ll a[MAX], ans[MAX];
pll rng[MAX];

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    ll mx = 0, mn = 0, now = 0;
    for(int i = 1;i <= q;i++){
        ll x;
        cin >> x;
        now += x;
        mx = max(mx, now);
        mn = min(mn, now);
        rng[i] = {mn, mx};
    }
    ans[1] = -rng[q].F;
    ans[n] = rng[q].S;
    for(int i = 1;i < n;i++){
        ll l = 0, r = q + 1;
        while(l < r){
            int mid = (r - l) / 2 + l;
            if(a[i] + rng[mid].S <= a[i + 1] + rng[mid].F)
                l = mid + 1;
            else
                r = mid;
        }
        l--;
        // cout << i << " " << l << '\n';
        ans[i] += rng[l].S;
        ans[i + 1] += -rng[l].F;
        if(l == q)
            continue;
        if(rng[l + 1].S > rng[l].S)
            ans[i] += (rng[l + 1].F + a[i + 1]) - (rng[l].S + a[i]);
        else
            ans[i + 1] += (a[i + 1] + rng[l].F) - (a[i] + rng[l].S);
    }
    for(int i = 1;i <= n;i++)
        cout << ans[i] << '\n';
}

int main(){
    IOS
	// CASE
	    solve();
    return 0;
}
/*
10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6
1 -3 0
2 -3 0
3 -3 2
4 -3 2
5 -4 2
6 -4 6
7 -7 6
8 -8 6
9 -8 6
10 -8 7
1 7
2 2
3 5
4 5
5 9
6 4
7 6
8 5
9 2
14
8
7
9
13
10
9
8
5
10
*/

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