Submission #576147

#	Time	Username	Problem	Language	Result	Execution time	Memory
576147		ddy888	Snowball (JOI21_ho_t2)	C++17	33 / 100	2528 ms	8516 KiB

Main

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define si second
typedef pair<ll,ll> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 100010;

int n, q;
ll arr[MAXN];
ll ans[MAXN];
vector<pi> ld, rd;

bool look_left(ll x, int i) {
    auto ff = lower_bound(ld.begin(), ld.end(), pi(arr[i] - x, 0));
    if (ff == ld.end()) return false;
    if (i > 1) {
        auto ss = lower_bound(rd.begin(), rd.end(), pi(x - arr[i - 1] + 1, 0));
        if (ss == rd.end()) return true;
        return (ff->si < ss->si);
    } 
    return true;
}

bool look_right(ll x, int i) {
    auto ff = lower_bound(rd.begin(), rd.end(), pi(x - arr[i], 0));
    if (ff == rd.end()) return false;
    if (i < n) {
        auto ss = lower_bound(ld.begin(), ld.end(), pi(arr[i + 1] - x + 1, 0));
        if (ss == ld.end()) return true;
        return (ff->si < ss->si);
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> arr[i];

    ld.pb({0, 0});
    rd.pb({0, 0});
    ll coord = 0;
    for (int i = 1; i <= q; ++i) {
        ll x; cin >> x;
        coord += x;
        if (coord < 0) {
            if (-coord > ld.back().fi) ld.pb({-coord, i});
        } else {
            if (coord > rd.back().fi) rd.pb({coord, i});
        }
    }
    arr[0] = arr[1] - ld.back().fi;
    arr[n + 1] = arr[n] + rd.back().fi;

    for (int i = 1; i <= n; ++i) {
        ll lo = arr[i - 1] - 1;
        ll hi = arr[i];
        ll lx, rx;

        while (lo + 1 < hi) {
            ll mid = (lo + hi) >> 1ll;
            if (look_left(mid, i)) hi = mid;
            else lo = mid;
        }
        lx = hi;
        lo = arr[i];
        hi = arr[i + 1] + 1;

        while (lo + 1 < hi) {
            ll mid = (lo + hi) >> 1ll;
            if (look_right(mid, i)) lo = mid;
            else hi = mid;
        }
        rx = lo;
        ans[i] = rx - lx;
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
    return 0;
}

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