oj.uz

답안 #1098961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1098961 2024-10-10T11:37:24 Z gyg Measures (CEOI22_measures) C++17
76 / 100
 475 ms 31640 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;
        bool operator<(Rng oth) const {
            if (l == oth.l && r == oth.r) assert(false);
            if (l == oth.l) return r < oth.r;
            return l < oth.l;
        }
    };
    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 = ps[i] - qry1(1, ind[i] - 1) * d;
        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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 29544 KB Output is correct
2 Correct 355 ms 31384 KB Output is correct
3 Correct 341 ms 31396 KB Output is correct
4 Correct 328 ms 29228 KB Output is correct
5 Correct 332 ms 30568 KB Output is correct
6 Correct 341 ms 29460 KB Output is correct
7 Correct 343 ms 30428 KB Output is correct
8 Correct 355 ms 29288 KB Output is correct
9 Correct 359 ms 29292 KB Output is correct
10 Correct 369 ms 31596 KB Output is correct
11 Correct 358 ms 30036 KB Output is correct
12 Correct 351 ms 31080 KB Output is correct
13 Correct 334 ms 29288 KB Output is correct
14 Correct 345 ms 31088 KB Output is correct
15 Correct 359 ms 30896 KB Output is correct
16 Correct 337 ms 28816 KB Output is correct
17 Correct 336 ms 30568 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 29544 KB Output is correct
2 Correct 355 ms 31384 KB Output is correct
3 Correct 341 ms 31396 KB Output is correct
4 Correct 328 ms 29228 KB Output is correct
5 Correct 332 ms 30568 KB Output is correct
6 Correct 341 ms 29460 KB Output is correct
7 Correct 343 ms 30428 KB Output is correct
8 Correct 355 ms 29288 KB Output is correct
9 Correct 359 ms 29292 KB Output is correct
10 Correct 369 ms 31596 KB Output is correct
11 Correct 358 ms 30036 KB Output is correct
12 Correct 351 ms 31080 KB Output is correct
13 Correct 334 ms 29288 KB Output is correct
14 Correct 345 ms 31088 KB Output is correct
15 Correct 359 ms 30896 KB Output is correct
16 Correct 337 ms 28816 KB Output is correct
17 Correct 336 ms 30568 KB Output is correct
18 Correct 459 ms 29548 KB Output is correct
19 Correct 432 ms 31592 KB Output is correct
20 Correct 368 ms 31340 KB Output is correct
21 Correct 374 ms 29292 KB Output is correct
22 Correct 376 ms 29804 KB Output is correct
23 Correct 337 ms 29548 KB Output is correct
24 Correct 426 ms 30056 KB Output is correct
25 Correct 358 ms 29292 KB Output is correct
26 Correct 448 ms 29160 KB Output is correct
27 Correct 475 ms 31640 KB Output is correct
28 Correct 376 ms 29544 KB Output is correct
29 Correct 417 ms 30832 KB Output is correct
30 Correct 400 ms 29032 KB Output is correct
31 Correct 391 ms 31132 KB Output is correct
32 Correct 370 ms 31084 KB Output is correct
33 Correct 452 ms 28780 KB Output is correct
34 Correct 398 ms 30568 KB Output is correct