Submission #1165020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165020		vincentbucourt1	Snowball (JOI21_ho_t2)	C++20	100 / 100	95 ms	9916 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define f first
#define s second

const int MAXN = 200'020;
const int INF = (int)1e18;

int N, Q;
int pos[MAXN];
int wind[MAXN];
pair<int,int> res[MAXN];
vector<int> dist;

pair<int,int> move (int l, int r, int d) {
    int newL = max(l, min(r, l + d));
    int newR = min(r, max(l, r + d));
    return {newL, newR};
}

signed main() {
    fastIO();
    cin >> N >> Q;
    dist.push_back(2*INF);
    for (int i = 0; i < N; i++) {
        cin >> pos[i];
        if (i != 0) {
            dist.push_back(pos[i] - pos[i-1]);
        }
    }
    for (int i = 0; i < Q; i++) {
        cin >> wind[i];
    }
    sort(dist.begin(), dist.end());
    int leftOn = 0, rightOn = 0;
    int farL = 0, farR = 0;
    int lastDist = 0;
    int iWind = 0;
    for (int iD = 0; iD < (int)dist.size(); iD++) {
        int distOn = dist[iD];
        farR += distOn-lastDist;
        rightOn += distOn-lastDist;
        while (iWind < Q && max(farL, min(farR, leftOn + wind[iWind])) < min(farR, max(farL, rightOn + wind[iWind]))) {
            farL = max(farL, min(farR, leftOn + wind[iWind]));
            farR = min(farR, max(farL, rightOn + wind[iWind]));
            leftOn += wind[iWind];
            rightOn += wind[iWind];
            iWind++;
        }
        int ansL = farL;
        int ansR = farR;
        if (iWind < Q) {
            ansL = max(farL, min(farR, leftOn + wind[iWind]));
            ansR = min(farR, max(farL, rightOn + wind[iWind]));
        }
        res[iD] = {ansL, (distOn - ansR)};
        lastDist = distOn;
    }
    // for (int i = 0; i < (int)dist.size(); i++) cerr << dist[i] << " " << res[i].f << " " << res[i].s << "\n";
    // cerr << "\n";
    for (int i = 0; i < N; i++) {
        int ans = 0;
        int l = -INF, r = INF;
        if (i != 0) l = pos[i-1];
        if (i != N-1) r = pos[i+1];
        int id = lower_bound(dist.begin(), dist.end(), pos[i]-l) - dist.begin();
        ans += res[id].s;
        id = lower_bound(dist.begin(), dist.end(), r-pos[i]) - dist.begin();
        ans += res[id].f;
        cout << ans << "\n";
    }
}

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