Submission #814640

#TimeUsernameProblemLanguageResultExecution timeMemory
814640CookieSnowball (JOI21_ho_t2)C++14
100 / 100
70 ms13944 KiB
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
// int y[4] = {0, 0, 1, -1};
const ll mod = 1e15 + 7, inf = 1e16;
const int mxn = 2e5 + 5;
int n, q;
ll x[mxn + 1], ans[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)cin >> x[i];
    vt<pll>seg;
    for(int i = 1; i < n; i++){
        seg.pb(make_pair(x[i + 1] - x[i], i));
    }
    sort(seg.begin(), seg.end());
    ll mx = 0, mn = 0, p = 0;
    int r = 0;
    for(int i = 1; i <= q; i++){
        ll w; cin >> w; 
        p += w;
        mx = max(mx, p); mn = min(mn, p);
        while(r < sz(seg) && seg[r].first <= mx + abs(mn)){
            int id = seg[r].second;
            if(w < 0){
                ans[id] += mx; ans[id + 1] += (seg[r].first - mx);
            }else{
                ans[id + 1] += abs(mn); ans[id] += (seg[r].first - abs(mn));
            }
            r++;
        }
        
    }
    for(int i = r; i < sz(seg); i++){
        int id = seg[i].second;
        ans[id] += mx; ans[id + 1] += abs(mn);
    }
    ans[n] += mx; ans[1] += abs(mn);
    for(int i = 1; i <= n; i++)cout << ans[i] << "\n";
    return(0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...