제출 #1175619

#제출 시각아이디문제언어결과실행 시간메모리
1175619clemmy14Snowball (JOI21_ho_t2)C++20
100 / 100
138 ms8220 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
	int n, q; cin >> n >> q;
    vector<int> x(n);
    for(int i=0; i<n; i++) cin >> x[i];

    vector<pair<int, int>> dis;
    for(int i=1; i<n; i++) dis.push_back({x[i]-x[i-1], i});
    sort(dis.begin(), dis.end());

    vector<int> ans(n, 0);
    int mxR=0, mxL=0, cur=0, idx=0;
    while(q--) {
        int w; cin >> w;
        cur+=w;
        if(cur > mxR) {
            while(idx < dis.size() && dis[idx].first <= cur+mxL) {
                ans[dis[idx].second-1]+=dis[idx].first-mxL;
                ans[dis[idx].second]+=mxL;
                idx++;
            }
            mxR=cur;
        }else if (-cur > mxL) {
            while(idx < dis.size() && dis[idx].first <= mxR-cur) {
                ans[dis[idx].second-1]+=mxR; 
                ans[dis[idx].second]+=dis[idx].first-mxR;
                idx++;
            }
            mxL=-cur;
        }
    }
    while(idx < dis.size()) {
		ans[dis[idx].second-1]+=mxR;
        ans[dis[idx].second]+=mxL;
        idx++;
    }
    ans[0]+=mxL; ans[n-1]+=mxR;
    for(int i=0; i<n; i++) cout << ans[i] << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...