Submission #382636

#	Time	Username	Problem	Language	Result	Execution time	Memory
382636		jainbot27	Snowball (JOI21_ho_t2)	C++17	100 / 100	132 ms	19524 KiB

Main

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

using ll = long long;

#define F0R(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ROF(i, a, b) for(int i=b-1; i>=a; i--)
#define siz(x) (int) x.size()
#define f first 
#define s second

const int mxN = 2e5+10;
const ll infLL = 1e18+10;

int n, q;
ll x[mxN];
ll w[mxN];
ll ans[mxN];
ll dl[mxN], dr[mxN];
pair<ll, int> sl[mxN], sr[mxN];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    F0R(i, n) cin >> x[i];
    F0R(i, q) cin >> w[i];
    // we will first solve for prefixs and then suffixs
    ll mn = 0, mx = 0;
    ll pos = 0;
    //F0R(i, q){
    //    pos += w[i];
    //    mn = min(mn, pos);
    //    mx = max(mx, pos);
    //}
    // find min and max
    //F0R(i, n) ans[i] += mn+mx;
    // init 
    dl[0] = infLL;
    FOR(i, 1, n) dl[i] = x[i]-x[i-1];
    dr[n-1] = infLL;
    F0R(i, n-1) dr[i] = x[i+1]-x[i];
    F0R(i, n) sl[i] = {dl[i], i}, sr[i] = {dr[i], i};
    sort(sl, sl+n); sort(sr, sr+n);
    //mn = 0, mx = 0, pos = 0;
    int pl = 0, pr = 0;
    F0R(i, q){
        pos += w[i];
        while(pl<n&&sl[pl].f<=mx-pos){
            ans[sl[pl].s] += max(-mn, sl[pl].f-mx);
            pl++;
        }
        while(pr<n&&sr[pr].f<=pos-mn){
            ans[sr[pr].s] += max(mx, sr[pr].f+mn);
            pr++;
        }
        mn = min(mn, pos);
        mx = max(mx, pos);
    }
    while(pl<n){
        ans[sl[pl].s] += -mn;
        pl++;
    }
    while(pr<n){
        ans[sr[pr].s] += mx;
        pr++;
    }
    F0R(i, n){
        cout << ans[i] << "\n";
    }
}

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