Submission #1290763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290763		stefanneagu	Measures (CEOI22_measures)	C++20	10 / 100	4 ms	3784 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5 + 1, mod = 1e9 + 7, inf = 1e18;

int n;

struct AINT {
    pair<int, int> aint[nmax];
    int bagat[nmax];
    int lz[nmax];

    void init() {
        for (int i = 1; i <= n * 4; i++) {
            aint[i] = {inf, -inf};
        }
    }

    void lazy(int nod, int st, int dr) {
        if (st != dr) {
            lz[nod * 2] += lz[nod];
            lz[nod * 2 + 1] += lz[nod];
            aint[nod * 2].first += lz[nod];
            aint[nod * 2 + 1].first += lz[nod];
            aint[nod * 2].second += lz[nod];
            aint[nod * 2 + 1].second += lz[nod];
        }
        lz[nod] = 0;
    }

    void setval(int i, int val, int nod = 1, int st = 1, int dr = n) {
        lazy(nod, st, dr);
        if (st == dr) {
            // cout << "!" << i << ": " << val << '\n';
            aint[nod] = {val, val};
            bagat[nod] = 1;
            return;
        }
        int mid = (st + dr) / 2;
        if (i <= mid) {
            setval(i, val, nod * 2, st, mid);
        } else {
            setval(i, val, nod * 2 + 1, mid + 1, dr);
        }
        aint[nod].first = min(aint[nod * 2].first, aint[nod * 2 + 1].first);
        aint[nod].second = max(aint[nod * 2].second, aint[nod * 2 + 1].second);
        bagat[nod] = bagat[nod * 2] + bagat[nod * 2 + 1];
    }

    void upd(int l, int r, int val, int nod = 1, int st = 1, int dr = n) {
        lazy(nod, st, dr);
        if (dr < l || r < st) {
            return;
        }
        if (l <= st && dr <= r) {
            aint[nod].first += val;
            aint[nod].second += val;
            lz[nod] += val;
            lazy(nod, st, dr);
            return;
        }
        int mid = (st + dr) / 2;
        upd(l, r, val, nod * 2, st, mid);
        upd(l, r, val, nod * 2 + 1, mid + 1, dr);
        aint[nod].first = min(aint[nod * 2].first, aint[nod * 2 + 1].first);
        aint[nod].second = max(aint[nod * 2].second, aint[nod * 2 + 1].second);
    }

    int qry(int l, int r, bool tip, int nod = 1, int st = 1, int dr = n) {
        lazy(nod, st, dr);
        if (dr < l || r < st) {
            if (tip == 0) {
                return inf;
            }
            return -inf;
        }
        if (l <= st && dr <= r) {
            if (tip == 0) {
                return aint[nod].first;
            }
            return aint[nod].second;
        }
        int mid = (st + dr) / 2;
        if (tip == 0) {
            return min(qry(l, r, tip, nod * 2, st, mid), qry(l, r, tip, nod * 2 + 1, mid + 1, dr));
        }
        return max(qry(l, r, tip, nod * 2, st, mid), qry(l, r, tip, nod * 2 + 1, mid + 1, dr));
    }

    int bagat_qry(int l, int r, int nod = 1, int st = 1, int dr = n) {
        lazy(nod, st, dr);
        if (dr < l || r < st) {
            return 0;
        }
        if (l <= st && dr <= r) {
            return bagat[nod];
        }
        int mid = (st + dr) / 2;
        return bagat_qry(l, r, nod * 2, st, mid) + bagat_qry(l, r, nod * 2 + 1, mid + 1, dr);
    }
} ds;

int v[nmax];
int nv[nmax];

void norm() {
    vector<pair<int, int>> vp;
    for (int i = 1; i <= n; i++) {
        vp.push_back({v[i], i});
    }
    sort(vp.begin(), vp.end());
    for (int i = 1; i <= n; i++) {
        nv[i] = 1 + lower_bound(vp.begin(), vp.end(), pair<int, int>{v[i], i}) - vp.begin();
    }
}

int32_t main() {
    // ifstream cin("dishes.in");
    // ofstream cout("dishes.out");
    int pre, d;
    cin >> pre >> n >> d;
    n += pre;
    ds.init();
    for (int i = 1; i <= pre; i++) {
        cin >> v[i];
    }
    for (int i = pre + 1; i <= n; i++) {
        cin >> v[i];
    }
    norm();
    int ans = 0;
    /*for (int j = 1; j <= n; j++) {
        int x = ds.qry(j, j, 1);
        if (-100 >= x) {
            cout << "- ";
        } else {
            cout << x << " ";
        }
    }
    cout << '\n';*/
    for (int i = 1; i <= n; i++) {
        int mai_mici = 0;
        if (nv[i] != 1) {
            mai_mici = ds.bagat_qry(1, nv[i] - 1);
        }
        int cur = v[i] - mai_mici * d;
        ds.setval(nv[i], cur);
        if (nv[i] != n) {
            ds.upd(nv[i] + 1, n, -d);
        }
        /*for (int j = 1; j <= n; j++) {
            int x = ds.qry(j, j, 1);
            if (-100 >= x) {
                cout << "- ";
            } else {
                cout << x << " ";
            }
        }
        cout << '\n';*/
        ans = max(ans, ds.qry(1, nv[i], 1) - ds.qry(nv[i], n, 0));
        if (i > pre) {
            if (ans % 2 == 0) {
                cout << ans / 2 << " ";
            } else {
                double d_ans = ans;
                d_ans /= 2;
                cout << fixed << setprecision(1) << d_ans << " ";
            }
        }
    }
    return 0;
}

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