oj.uz

Submission #1016679

# Submission time Handle Problem Language Result Execution time Memory
1016679 2024-07-08T10:19:13 Z LOLOLO Measures (CEOI22_measures) C++17
100 / 100
 286 ms 45512 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 100;
ll st[N * 4][4], n, m, d;
int a[N];

void upd(int id, int l, int r, int p, int val) {
    if (l == r) {
        st[id][0] = 1;
        st[id][1] = val - d;
        st[id][2] = val - d;
        st[id][3] = 0;
        return;
    }

    int m = (l + r) / 2;
    if (m >= p) {
        upd(id * 2, l, m, p, val);
    } else {
        upd(id * 2 + 1, m + 1, r, p, val);
    }

    st[id][0] = st[id * 2][0] + st[id * 2 + 1][0];
    st[id][1] = max(st[id * 2][1], st[id * 2 + 1][1] - st[id * 2][0] * d);
    st[id][2] = min(st[id * 2][2], st[id * 2 + 1][2] - st[id * 2][0] * d);
    st[id][3] = max({st[id * 2][1] - st[id * 2 + 1][2] + st[id * 2][0] * d, st[id * 2][3], st[id * 2 + 1][3]});
}

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

    cin >> n >> m >> d;

    vector <pair <int, int>> A;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        A.pb({a[i], i});
    }

    for (int i = n + 1; i <= n + m; i++) {
        cin >> a[i];
        A.pb({a[i], i});
    }

    for (int i = 0; i < N * 4; i++) {
        st[i][1] = -1e16;
        st[i][2] = 1e16;
    }

    sort(all(A));
    map <pair <int, int>, int> mp;
    int cnt = 1;
    for (auto x : A) {
        mp[x] = cnt;
        cnt++;
    }

    for (int i = 1; i <= n + m; i++) {
        upd(1, 1, n + m, mp[{a[i], i}], a[i]);
        if (i > n) {
            ll t = max((ll)0, st[1][3]);
            if (t % 2 == 0) {
                cout << t / 2 << " ";
            } else {
                cout << t / 2 << ".5 ";
            }
        } 
    }

    return 0;
} 

// dp[l][r][k1][k2]
//

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26204 KB Output is correct
2 Correct 5 ms 26084 KB Output is correct
3 Correct 11 ms 25692 KB Output is correct
4 Correct 10 ms 25472 KB Output is correct
5 Correct 9 ms 25688 KB Output is correct
6 Correct 10 ms 25692 KB Output is correct
7 Correct 10 ms 25588 KB Output is correct
8 Correct 10 ms 25672 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26204 KB Output is correct
2 Correct 5 ms 26084 KB Output is correct
3 Correct 11 ms 25692 KB Output is correct
4 Correct 10 ms 25472 KB Output is correct
5 Correct 9 ms 25688 KB Output is correct
6 Correct 10 ms 25692 KB Output is correct
7 Correct 10 ms 25588 KB Output is correct
8 Correct 10 ms 25672 KB Output is correct
9 Correct 265 ms 42184 KB Output is correct
10 Correct 242 ms 42180 KB Output is correct
11 Correct 123 ms 42180 KB Output is correct
12 Correct 173 ms 42184 KB Output is correct
13 Correct 115 ms 41676 KB Output is correct
14 Correct 125 ms 42180 KB Output is correct
15 Correct 255 ms 41420 KB Output is correct
16 Correct 113 ms 42224 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 43208 KB Output is correct
2 Correct 123 ms 45252 KB Output is correct
3 Correct 129 ms 45256 KB Output is correct
4 Correct 128 ms 43048 KB Output is correct
5 Correct 125 ms 44200 KB Output is correct
6 Correct 129 ms 43464 KB Output is correct
7 Correct 138 ms 44204 KB Output is correct
8 Correct 129 ms 42952 KB Output is correct
9 Correct 123 ms 42948 KB Output is correct
10 Correct 123 ms 45348 KB Output is correct
11 Correct 120 ms 43720 KB Output is correct
12 Correct 135 ms 44848 KB Output is correct
13 Correct 149 ms 42924 KB Output is correct
14 Correct 152 ms 44912 KB Output is correct
15 Correct 160 ms 44808 KB Output is correct
16 Correct 146 ms 42564 KB Output is correct
17 Correct 135 ms 44228 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 43208 KB Output is correct
2 Correct 123 ms 45252 KB Output is correct
3 Correct 129 ms 45256 KB Output is correct
4 Correct 128 ms 43048 KB Output is correct
5 Correct 125 ms 44200 KB Output is correct
6 Correct 129 ms 43464 KB Output is correct
7 Correct 138 ms 44204 KB Output is correct
8 Correct 129 ms 42952 KB Output is correct
9 Correct 123 ms 42948 KB Output is correct
10 Correct 123 ms 45348 KB Output is correct
11 Correct 120 ms 43720 KB Output is correct
12 Correct 135 ms 44848 KB Output is correct
13 Correct 149 ms 42924 KB Output is correct
14 Correct 152 ms 44912 KB Output is correct
15 Correct 160 ms 44808 KB Output is correct
16 Correct 146 ms 42564 KB Output is correct
17 Correct 135 ms 44228 KB Output is correct
18 Correct 274 ms 43320 KB Output is correct
19 Correct 283 ms 44968 KB Output is correct
20 Correct 137 ms 45256 KB Output is correct
21 Correct 166 ms 43188 KB Output is correct
22 Correct 192 ms 43460 KB Output is correct
23 Correct 153 ms 43224 KB Output is correct
24 Correct 286 ms 43956 KB Output is correct
25 Correct 154 ms 43084 KB Output is correct
26 Correct 230 ms 42936 KB Output is correct
27 Correct 216 ms 45512 KB Output is correct
28 Correct 165 ms 43468 KB Output is correct
29 Correct 180 ms 44744 KB Output is correct
30 Correct 163 ms 42868 KB Output is correct
31 Correct 166 ms 45000 KB Output is correct
32 Correct 131 ms 44744 KB Output is correct
33 Correct 224 ms 42528 KB Output is correct
34 Correct 163 ms 44228 KB Output is correct