제출 #1357752

#제출 시각아이디문제언어결과실행 시간메모리
1357752channkSnowball (JOI21_ho_t2)C++20
100 / 100
61 ms9908 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2,fma") 
#define ll long long
#define gcd __gcd
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ts cin.tie(nullptr)->sync_with_stdio(false);
#define debug cout<<"HI"<<endl;
const int inf = 1e9;
const ll infll = 1e18;
 
using namespace std;
ll n,q,x[200005],res[200005];

int main(){
    ts
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> x[i];
    x[0]=-infll; x[n+1]=infll;
    
    ll cur=0, high=0, low=0;
    vector<tuple<ll,ll,bool>> rec;
    for(int i=0;i<q;i++){
        ll w; cin >> w;
        cur+=w;
        if(cur>high) high=cur, rec.push_back({high-low, high, false});
        if(cur<low) low=cur, rec.push_back({high-low, high, true});
    }
    for(int i=1;i<=n+1;i++){
        ll gap=x[i]-x[i-1];
        if(high-low<=gap){
            res[i-1]+=high;
            res[i]+=abs(low);
            continue;
        }
        auto [sm,h,t]=*lower_bound(all(rec),make_tuple(gap,(ll)-infll,false));
        ll curhigh=h, curlow=sm-h;
        if(!t) curhigh=gap-curlow;
        else curlow=gap-curhigh;
        res[i-1]+=curhigh;
        res[i]+=abs(curlow);
    }
    for(int i=1;i<=n;i++) cout << res[i] << "\n";
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…