제출 #997386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997386		vjudge1	Measures (CEOI22_measures)	C++17	100 / 100	444 ms	50096 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll
using vi = vector<int>;
using ii = pair<int, int>;
const ll INF = 1e18;

struct AINT {
    int n;
    vi Mi, Ma, Re, Lz;

    AINT(int N) : n(N), Mi(4 * N, 0), Ma(4 * N, 0), Re(4 * N, 0), Lz(4 * N, 0) {}

    void prop(int u, int s, int d) {
        Mi[u] += Lz[u];
        Ma[u] += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void update(int l, int r, int v, int u, int s, int d) {
        prop(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            Lz[u] += v;
            prop(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);

        Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
        Ma[u] = max(Ma[u << 1], Ma[u << 1 | 1]);
        Re[u] = max({Re[u << 1], Re[u << 1 | 1], Ma[u << 1 | 1] - Mi[u << 1]});
    }

    void update(int l, int r, int v) { update(l, r, v, 1, 0, n - 1); }

    int query() { return Re[1]; }
};

struct solver {
    int n, d, rez;
    vi V, pozInA;
    vector<ii> A;
    set<int> Active;

    AINT Sol;

    solver(int N, vi V0, int D) : n(N), d(D), rez(0), V(V0), Sol(N + 1) {
        for(int i = 0; i < n; ++i) {
            A.push_back({V[i], i});
        }
        V.push_back(-INF);
        A.push_back({-INF, n});
        ++n;
        sort(A.begin(), A.end());
        pozInA.resize(n);
        for(int i = 0; i < n; ++i)
            pozInA[A[i].second] = i;

        Active.insert(0);
    }

    void enable(int p) {
        int pA = pozInA[p];
        auto ant = *(--Active.lower_bound(pA)); /// pozitia anterioriului in A
        int dist1 = V[p] - A[ant].first, v1 = (d - dist1) / 2;
        Sol.update(pA, n, v1);

        auto urm = Active.lower_bound(pA);
        if(urm != Active.end()) {
            int purm = *urm;
            int dist2 = A[purm].first - V[p], v2 = (d - dist2) / 2;
            int dist_ant = A[purm].first - A[ant].first, vant = (d - dist_ant) / 2;
            Sol.update(purm, n, v2 - vant);
        }

        Active.insert(pA);
        rez = max(rez, Sol.query());
    }
};

signed main() {
    int n, m, d;
    cin >> n >> m >> d;

    vi V(n + m);
    d *= 2;
    for(int i = 0; i < n + m; ++i) {
        cin >> V[i];
        V[i] *= 2;
    }
    
    solver S(n + m, V, d);

    for(int i = 0; i < n; ++i) S.enable(i);

    for(int i = 0; i < m; ++i) {
        S.enable(i + n);
        int r = S.rez;
        cout << r / 2;
        if(r & 1) cout << ".5 ";
        else cout << " ";
    }
    cout << "\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41