oj.uz

Submission #1098965

# Submission time Handle Problem Language Result Execution time Memory
1098965 2024-10-10T11:40:58 Z gyg Measures (CEOI22_measures) C++17
100 / 100
 495 ms 31680 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 708 KB Output is correct
8 Correct 2 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 708 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 310 ms 31672 KB Output is correct
10 Correct 267 ms 31672 KB Output is correct
11 Correct 201 ms 31512 KB Output is correct
12 Correct 250 ms 31416 KB Output is correct
13 Correct 190 ms 31036 KB Output is correct
14 Correct 195 ms 31544 KB Output is correct
15 Correct 254 ms 30952 KB Output is correct
16 Correct 210 ms 31672 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 29532 KB Output is correct
2 Correct 354 ms 31340 KB Output is correct
3 Correct 348 ms 31336 KB Output is correct
4 Correct 348 ms 29316 KB Output is correct
5 Correct 330 ms 30568 KB Output is correct
6 Correct 361 ms 29496 KB Output is correct
7 Correct 350 ms 30552 KB Output is correct
8 Correct 355 ms 29292 KB Output is correct
9 Correct 331 ms 29080 KB Output is correct
10 Correct 386 ms 31584 KB Output is correct
11 Correct 353 ms 30060 KB Output is correct
12 Correct 397 ms 30920 KB Output is correct
13 Correct 388 ms 29296 KB Output is correct
14 Correct 347 ms 31084 KB Output is correct
15 Correct 385 ms 30992 KB Output is correct
16 Correct 356 ms 28828 KB Output is correct
17 Correct 360 ms 30572 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 29532 KB Output is correct
2 Correct 354 ms 31340 KB Output is correct
3 Correct 348 ms 31336 KB Output is correct
4 Correct 348 ms 29316 KB Output is correct
5 Correct 330 ms 30568 KB Output is correct
6 Correct 361 ms 29496 KB Output is correct
7 Correct 350 ms 30552 KB Output is correct
8 Correct 355 ms 29292 KB Output is correct
9 Correct 331 ms 29080 KB Output is correct
10 Correct 386 ms 31584 KB Output is correct
11 Correct 353 ms 30060 KB Output is correct
12 Correct 397 ms 30920 KB Output is correct
13 Correct 388 ms 29296 KB Output is correct
14 Correct 347 ms 31084 KB Output is correct
15 Correct 385 ms 30992 KB Output is correct
16 Correct 356 ms 28828 KB Output is correct
17 Correct 360 ms 30572 KB Output is correct
18 Correct 441 ms 29548 KB Output is correct
19 Correct 484 ms 31340 KB Output is correct
20 Correct 374 ms 31292 KB Output is correct
21 Correct 396 ms 29308 KB Output is correct
22 Correct 456 ms 29584 KB Output is correct
23 Correct 352 ms 29548 KB Output is correct
24 Correct 495 ms 30056 KB Output is correct
25 Correct 344 ms 29100 KB Output is correct
26 Correct 466 ms 29288 KB Output is correct
27 Correct 470 ms 31680 KB Output is correct
28 Correct 394 ms 29548 KB Output is correct
29 Correct 419 ms 30884 KB Output is correct
30 Correct 380 ms 29032 KB Output is correct
31 Correct 374 ms 31184 KB Output is correct
32 Correct 345 ms 31084 KB Output is correct
33 Correct 409 ms 28780 KB Output is correct
34 Correct 411 ms 30568 KB Output is correct