Submission #1161270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161270		brinton	Snowball (JOI21_ho_t2)	C++20	100 / 100	65 ms	11448 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int N,Q;
    cin >> N >> Q;
    vector<int> v(N);
    for(auto &i:v)cin >> i;
    int pos = 0;
    int neg = 0;
    int cur = 0;
    vector<int> modify;
    for(int i = 0;i < Q;i++){
        int w;cin >> w;
        cur += w;
        if(cur > pos){
            modify.push_back(cur-pos);
            pos = cur;
        }
        if(cur < neg){
            modify.push_back(cur-neg);
            neg = cur;
        }
    }
    vector<int> ans(N,0);
    ans[0] += -neg;
    ans[N-1] += pos;
    vector<int> all = modify;
    vector<int> posPre = modify;
    vector<int> negPre = modify;
    for(int i = 0;i < all.size();i++){
        all[i] = abs(all[i]);
        posPre[i] = max(0LL,posPre[i]);
        negPre[i] = max(0LL,-negPre[i]);
        if(i != 0){
            all[i] += all[i-1];
            posPre[i] += posPre[i-1];
            negPre[i] += negPre[i-1];
        }
    }
    // for(auto i:modify)cout << i << " "; cout << endl;
    // for(auto i:all)cout << i << " "; cout << endl;
    // for(auto i:posPre)cout << i << " "; cout << endl;
    // for(auto i:negPre)cout << i << " "; cout << endl;
    for(int i = 1;i < N;i++){
        // pos give to i-1;
        // neg gives to i;
        auto it = lower_bound(all.begin(),all.end(),v[i]-v[i-1]);
        int range = it-all.begin()-1;// to here
        int usage = 0;
        if(range >= 0){
            ans[i-1] += posPre[range];
            ans[i] += negPre[range];
            usage = posPre[range]+negPre[range];
        }
        if(it != all.end()){
            // range+1
            if(modify[range+1] < 0){
                // neg
                ans[i] += v[i]-v[i-1]-(usage);
            }else{
                ans[i-1] += v[i]-v[i-1]-(usage);
            }
        }
    }
    for(auto i:ans)cout << i << '\n';
}

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