Submission #1098965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098965		gyg	Measures (CEOI22_measures)	C++17	100 / 100	495 ms	31680 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vct vector 
#define pii pair<int, int>
#define fir first 
#define sec second 
const int N = 2e5 + 5, M = 2e5 + 5, INF = 1e18;

int n, m, d;
arr<int, N + M> ps;

arr<int, 4 * (N + M)> sgtr1;
void upd1(int i, int x, int u = 1, int lw = 1, int hg = n + m) {
    if (i < lw || hg < i) return;
    if (lw == hg) { sgtr1[u] += x; return; }
    int md = (lw + hg) / 2;
    upd1(i, x, 2 * u, lw, md), upd1(i, x, 2 * u + 1, md + 1, hg);
    sgtr1[u] = sgtr1[2 * u] + sgtr1[2 * u + 1];
}
int qry1(int l, int r, int u = 1, int lw = 1, int hg = n + m) {
    if (l > r) return 0;
    if (r < lw || hg < l) return 0;
    if (l <= lw && hg <= r) return sgtr1[u];
    int md = (lw + hg) / 2;
    return qry1(l, r, 2 * u, lw, md) + qry1(l, r, 2 * u + 1, md + 1, hg);
}

struct Nd { int mn, mx, lzy; };
Nd mrg(Nd x, Nd y) { return {min(x.mn, y.mn), max(x.mx, y.mx), 0}; }
arr<Nd, 4 * (N + M)> sgtr2;
void intl() {
    for (int u = 1; u <= 4 * (n + m); u++) sgtr2[u] = {INF, -INF, 0};
}
void prp(int u) {
    int inc = sgtr2[u].lzy;
    for (int v : {2 * u, 2 * u + 1})
        sgtr2[v].mn += inc, sgtr2[v].mx += inc, sgtr2[v].lzy += inc; 
    sgtr2[u].lzy = 0;
}
void add_upd2(int l, int r, int x, int u = 1, int lw = 1, int hg = n + m) {
    if (r < lw || hg < l) return;
    if (l <= lw && hg <= r) { sgtr2[u].mn += x, sgtr2[u].mx += x, sgtr2[u].lzy += x; return; }
    prp(u);
    int md = (lw + hg) / 2;
    add_upd2(l, r, x, 2 * u, lw, md), add_upd2(l, r, x, 2 * u + 1, md + 1, hg);
    sgtr2[u].mn = min(sgtr2[2 * u].mn, sgtr2[2 * u + 1].mn);
    sgtr2[u].mx = max(sgtr2[2 * u].mx, sgtr2[2 * u + 1].mx);
}
void st_upd2(int i, int x, int u = 1, int lw = 1, int hg = n + m) {
    if (i < lw || hg < i) return;
    if (lw == hg) { sgtr2[u] = {x, x, 0}; return; }
    prp(u);
    int md = (lw + hg) / 2;
    st_upd2(i, x, 2 * u, lw, md), st_upd2(i, x, 2 * u + 1, md + 1, hg);
    sgtr2[u].mn = min(sgtr2[2 * u].mn, sgtr2[2 * u + 1].mn);
    sgtr2[u].mx = max(sgtr2[2 * u].mx, sgtr2[2 * u + 1].mx);
}
Nd qry2(int l, int r, int u = 1, int lw = 1, int hg = n + m) {
    if (r < lw || hg < l) return {INF, -INF, 0};
    if (l <= lw && hg <= r) return sgtr2[u];
    prp(u);
    int md = (lw + hg) / 2;
    return mrg(qry2(l, r, 2 * u, lw, md), qry2(l, r, 2 * u + 1, md + 1, hg));
}

arr<int, N + M> ind;
void prcmp() {
    vct<pii> ord;
    for (int i = 1; i <= n + m; i++) 
        ord.push_back({ps[i], i});
    sort(ord.begin(), ord.end());
    for (int i = 0; i < ord.size(); i++) ind[ord[i].sec] = i + 1;

    intl();
    for (int i = 1; i <= n; i++) upd1(ind[i], 1);
    for (int i = 1; i <= n; i++) {
        int vl = ps[i] - qry1(1, ind[i] - 1) * d;
        st_upd2(ind[i], vl);
    }
}

int gt_ans() {
    struct Rng { int l, r, mn, mx; };
    Rng rng = {0, 0, INF, -INF};
    int ans = 0;
    for (int i = 1; i <= n + m; i++) {
        if (qry1(i, i) == 0) continue;
        int vl = qry2(i, i).mn;
        if (vl > rng.mx) {
            if (rng.l != 0) { rng.r = i - 1; }
            rng = {i, 0, vl, vl};
        }
        rng.mn = min(rng.mn, vl);
        ans = max(ans, rng.mx - rng.mn);
    }
    return ans;
}

int ans;
void ins(int i) {
    int vl = ps[i] - qry1(1, ind[i] - 1) * d;
    upd1(ind[i], 1), st_upd2(ind[i], vl);
    add_upd2(ind[i] + 1, n + m, -d);
    ans = max({ans, qry2(1, ind[i] - 1).mx - qry2(ind[i], n + m).mn, qry2(1, ind[i]).mx - qry2(ind[i] + 1, n + m).mn});
}

signed main() {
    // freopen("ms.in", "r", stdin);
    cin >> n >> m >> d; 
    for (int i = 1; i <= n + m; i++) cin >> ps[i];

    prcmp();

    ans = gt_ans();
    for (int i = n + 1; i <= n + m; i++) {
        ins(i);
        cout << ans / 2;
        if (ans % 2 == 1) cout << ".5";
        cout << " ";
    }
}

Compilation message (stderr)

Main.cpp: In function 'void prcmp()':
Main.cpp:74:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < ord.size(); i++) ind[ord[i].sec] = i + 1;
      |                     ~~^~~~~~~~~~~~

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