Submission #974289

#	Time	Username	Problem	Language	Result	Execution time	Memory
974289		berr	Snowball (JOI21_ho_t2)	C++17	0 / 100	1 ms	532 KiB

Main

#include <bits/stdc++.h>
using namespace std; 
#define int long long

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int n, q; cin >> n >> q;

    vector<int> x(n), l(n), r(n);
    vector<int> mi(q), ma(q);

    for(auto &i: x) cin >> i;
    vector<int> op(q);

    for(int i=0; i<q; i++) cin >> op[i];

    for(int i=1; i<q; i++){
        op[i]+=op[i-1];
        mi[i]=mi[i-1]; ma[i] =ma[i-1];

        if(op[i] < op[mi[i]]) mi[i]=i;
        if(op[i] > op[ma[i]]) ma[i]=i;
    }

    l[0]=x[0]+op[mi[q-1]]; r[n-1] = x[n-1]+op[ma[q-1]];

    for(int i=0; i<n-1; i++){
        int s=-1;

        for(int l=20; l>=0; l--){
            int tmp = s+(1<<l);
            if(tmp >= q-1) continue;
            if(op[ma[tmp]] - op[mi[tmp]]>=x[i+1]-x[i]) continue;
            s=tmp;
        }

        s++;
        
        if(x[i]+op[ma[s]]>=x[i+1]+op[mi[s]]){            
            if(ma[s] < mi[s]){
                r[i]=x[i]+op[ma[s]];
                l[i+1]=r[i];
            }
            else{
                l[i+1]=x[i+1]+op[mi[s]];
                r[i]=l[i+1];

            }
        }
        else{

            r[i]=min(x[i+1], x[i]+op[ma[s]]);
            l[i+1]=max(x[i+1]+op[mi[s]], x[i]);
        }
    }
    for(int i=0; i<n; i++){
        l[i]=min(l[i], x[i]);
        r[i]=max(r[i], x[i]);
    }

    for(int i=0; i<n; i++) cout<<r[i]-l[i]<<"\n";
}

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