Submission #400190

#	Time	Username	Problem	Language	Result	Execution time	Memory
400190		nvmdava	Snowball (JOI21_ho_t2)	C++17	0 / 100	2 ms	460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll x[N];
vector<ll> loc;
ll ans[N];

bool sign(ll a, ll b){
    if(a > 0 && b > 0) return 1;
    if(a < 0 && b < 0) return 1;
    return 0;
}

ll get(ll a){
    int l = 1;
    int r = loc.size() - 1;
    if(sign(loc[r], a) && abs(loc[r]) + abs(loc[r - 1]) <= abs(a))
        return abs(loc[r]);
    if(sign(loc[r - 1], a) && abs(loc[r - 1]) + abs(loc[r - 2]) <= abs(a))
        return abs(loc[r - 1]);
    if(r <= 1) return 0;
    while(l != r){
        int m = (l + r) >> 1;
        if(abs(loc[m]) + abs(loc[m - 1]) >= abs(a)){
            r = m;
        } else {
            l = m + 1;
        }
    }
    int m = l;
    if(sign(loc[m], a))
        return abs(a + loc[m - 1]);
    else
        return abs(loc[m - 1]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin>>n>>q;
    for(int i = 1; i <= n; ++i)
        cin>>x[i];
    ll now = 0;
    loc.push_back(0);
    while(q--){
        ll t;
        cin>>t;
        now += t;
        if(now == 0) continue;
        if(sign(now, loc.back())){
            if(abs(now) > abs(loc.back())){
                loc.pop_back();
                loc.push_back(now);
            }
        } else {
            if(loc.size() <= 2 || abs(loc[loc.size() - 2]) < abs(now)){
                loc.push_back(now);
            }
        }
    }

    for(int i = 1; i < n; ++i){
        ans[i] += get(x[i + 1] - x[i]);
        ans[i + 1] += get(x[i] - x[i + 1]);
    }
    ans[n] += get(1'000'000'000'000'000'000);
    ans[1] += get(-1'000'000'000'000'000'000);
    for(int i = 1; i <= n; ++i)
        cout<<ans[i]<<'\n';
}

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