oj.uz

Submission #806883

# Submission time Handle Problem Language Result Execution time Memory
806883 2023-08-04T10:45:27 Z alextodoran Measures (CEOI22_measures) C++17
100 / 100
 166 ms 58740 KB 
/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int M_MAX = 200000;
const int X_MAX = N_MAX + M_MAX;
const ll INF = LLONG_MAX / 2;

int N, M, D;
int A[N_MAX + 2];
int B[M_MAX + 2];

int Aid[N_MAX + 2];
int Bid[M_MAX + 2];

int X;
pair <int, int> aux[X_MAX + 2];
void compress () {
    for (int i = 1; i <= N; i++) {
        aux[++X] = make_pair(A[i], i);
    }
    for (int i = 1; i <= M; i++) {
        aux[++X] = make_pair(B[i], N + i);
    }
    sort(aux + 1, aux + X + 1);
    for (int i = 1; i <= X; i++) {
        if (aux[i].second <= N) {
            Aid[aux[i].second] = i;
        } else {
            Bid[aux[i].second - N] = i;
        }
    }
}

struct SegInfo {
    ll mx, mn;
    ll maxDiff;
    ll lazy;
    SegInfo () {
        mx = -INF;
        mn = +INF;
        maxDiff = 0;
        lazy = 0;
    }
    void init (const int &val) {
        mx = mn = val - lazy;
        maxDiff = 0;
    }
    void add (const ll &val) {
        mx -= val;
        mn -= val;
        lazy += val;
    }
};
SegInfo operator + (const SegInfo &A, const SegInfo &B) {
    SegInfo C;
    C.mx = max(A.mx, B.mx);
    C.mn = min(A.mn, B.mn);
    C.maxDiff = max({A.maxDiff, B.maxDiff, A.mx - B.mn});
    C.lazy = 0;
    return C;
}

SegInfo segTree[X_MAX * 4 + 2];

void update (int node, int l, int r, int pos, int val) {
    if (l == r) {
        segTree[node].init(val);
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    segTree[left].add(segTree[node].lazy);
    segTree[right].add(segTree[node].lazy);
    if (pos <= mid) {
        update(left, l, mid, pos, val);
        segTree[right].add(D);
    } else {
        update(right, mid + 1, r, pos, val);
    }
    segTree[node] = segTree[left] + segTree[right];
}
void update (int pos, int val) {
    update(1, 1, X, pos, val);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> D;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= M; i++) {
        cin >> B[i];
    }
    compress();
    for (int i = 1; i <= N; i++) {
        update(Aid[i], A[i]);
    }
    for (int i = 1; i <= M; i++) {
        update(Bid[i], B[i]);
        ll t = segTree[1].maxDiff;
        if (t % 2 == 0) {
            cout << t / 2 << " ";
        } else {
            cout << t / 2 << ".5 ";
        }
    }
    cout << "\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50432 KB Output is correct
2 Correct 21 ms 50428 KB Output is correct
3 Correct 20 ms 50420 KB Output is correct
4 Correct 21 ms 50572 KB Output is correct
5 Correct 23 ms 50468 KB Output is correct
6 Correct 24 ms 50388 KB Output is correct
7 Correct 21 ms 50432 KB Output is correct
8 Correct 20 ms 50388 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50432 KB Output is correct
2 Correct 21 ms 50428 KB Output is correct
3 Correct 20 ms 50420 KB Output is correct
4 Correct 21 ms 50572 KB Output is correct
5 Correct 23 ms 50468 KB Output is correct
6 Correct 24 ms 50388 KB Output is correct
7 Correct 21 ms 50432 KB Output is correct
8 Correct 20 ms 50388 KB Output is correct
9 Correct 139 ms 55588 KB Output is correct
10 Correct 126 ms 55488 KB Output is correct
11 Correct 91 ms 55512 KB Output is correct
12 Correct 112 ms 55476 KB Output is correct
13 Correct 89 ms 55036 KB Output is correct
14 Correct 97 ms 55552 KB Output is correct
15 Correct 154 ms 54780 KB Output is correct
16 Correct 90 ms 55408 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 56496 KB Output is correct
2 Correct 104 ms 58388 KB Output is correct
3 Correct 109 ms 58352 KB Output is correct
4 Correct 97 ms 56264 KB Output is correct
5 Correct 107 ms 57536 KB Output is correct
6 Correct 99 ms 56560 KB Output is correct
7 Correct 105 ms 57564 KB Output is correct
8 Correct 98 ms 56344 KB Output is correct
9 Correct 96 ms 56140 KB Output is correct
10 Correct 104 ms 58596 KB Output is correct
11 Correct 99 ms 57064 KB Output is correct
12 Correct 102 ms 58056 KB Output is correct
13 Correct 103 ms 56240 KB Output is correct
14 Correct 102 ms 58148 KB Output is correct
15 Correct 104 ms 57936 KB Output is correct
16 Correct 94 ms 55800 KB Output is correct
17 Correct 102 ms 57508 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 56496 KB Output is correct
2 Correct 104 ms 58388 KB Output is correct
3 Correct 109 ms 58352 KB Output is correct
4 Correct 97 ms 56264 KB Output is correct
5 Correct 107 ms 57536 KB Output is correct
6 Correct 99 ms 56560 KB Output is correct
7 Correct 105 ms 57564 KB Output is correct
8 Correct 98 ms 56344 KB Output is correct
9 Correct 96 ms 56140 KB Output is correct
10 Correct 104 ms 58596 KB Output is correct
11 Correct 99 ms 57064 KB Output is correct
12 Correct 102 ms 58056 KB Output is correct
13 Correct 103 ms 56240 KB Output is correct
14 Correct 102 ms 58148 KB Output is correct
15 Correct 104 ms 57936 KB Output is correct
16 Correct 94 ms 55800 KB Output is correct
17 Correct 102 ms 57508 KB Output is correct
18 Correct 151 ms 56604 KB Output is correct
19 Correct 150 ms 58288 KB Output is correct
20 Correct 134 ms 58412 KB Output is correct
21 Correct 166 ms 56328 KB Output is correct
22 Correct 124 ms 56644 KB Output is correct
23 Correct 104 ms 56500 KB Output is correct
24 Correct 147 ms 57108 KB Output is correct
25 Correct 99 ms 56200 KB Output is correct
26 Correct 141 ms 56180 KB Output is correct
27 Correct 143 ms 58740 KB Output is correct
28 Correct 124 ms 56664 KB Output is correct
29 Correct 150 ms 58012 KB Output is correct
30 Correct 131 ms 56132 KB Output is correct
31 Correct 136 ms 58208 KB Output is correct
32 Correct 121 ms 58072 KB Output is correct
33 Correct 151 ms 55848 KB Output is correct
34 Correct 129 ms 57556 KB Output is correct