Submission #666934

#	Time	Username	Problem	Language	Result	Execution time	Memory
666934		Darren0724	Snowball (JOI21_ho_t2)	C++17	100 / 100	244 ms	17056 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
signed main(){
    int n,q;cin>>n>>q;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int left=0,right=0;
    int place=0;
    vector<int> pre(1),a(1),b(1),c(1);
    for(int i=0;i<q;i++){
        int k;cin>>k;
        place+=k;
        if(place>0){
            if(place>right){
                right=place;
                a.push_back(left);
                b.push_back(right);
                c.push_back(1);
                pre.push_back(left+right);
            }
        }
        if(place<0){
            if(abs(place)>left){
                left=-place;
                a.push_back(left);
                b.push_back(right);
                c.push_back(-1);
                pre.push_back(left+right);
            }
        }
    }
    vector<int> ans(n);
    ans[0]+=left;
    ans[n-1]+=right;
    int m=a.size();
    for(int i=0;i<n-1;i++){
        int p=v[i+1]-v[i];
        int it=lower_bound(all(pre),p)-pre.begin();
        if(it==m){
            ans[i]+=b[it-1];
            ans[i+1]+=a[it-1];
        }
        else{
            if(c[it]==1){
                ans[i]+=b[it-1]+p-pre[it-1];
                ans[i+1]+=a[it-1];
            }
            else{
                ans[i]+=b[it-1];
                ans[i+1]+=a[it-1]+p-pre[it-1];
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

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