oj.uz

Submission #927617

# Submission time Handle Problem Language Result Execution time Memory
927617 2024-02-15T07:19:43 Z math_rabbit_1028 Measures (CEOI22_measures) C++14
76 / 100
 296 ms 39844 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

int N, M;
ll D;
vector<pii> arr;
int ord[202020];

int cnt = 0;
struct segtree {
    ll lt[808080], rt[808080], mx[808080], sum[808080];
    void update(int v, int st, int ed, int idx, ll val) {
        if (st > idx || ed < idx) return;
        if (st == ed) {
            lt[v] = rt[v] = mx[v] = sum[v] = val;
            return;
        }
        int mid = (st+ed)/2;
        update(2*v, st, mid, idx, val);
        update(2*v+1, mid+1, ed, idx, val);

        lt[v] = max(lt[2*v], lt[2*v+1] + sum[2*v]);
        rt[v] = max(rt[2*v+1], rt[2*v] + sum[2*v+1]);
        mx[v] = max(mx[2*v], mx[2*v+1]);
        mx[v] = max(mx[v], rt[2*v]+lt[2*v+1]);
        sum[v] = sum[2*v] + sum[2*v+1];
    }
} seg;

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

    cin >> N >> M >> D;

    for (int i = 1; i <= M; i++) {
        int a; cin >> a;
        arr.push_back({a, i});
    }
    sort(arr.begin(), arr.end());
    for (int i = 0; i < M; i++) ord[arr[i].second] = i;
    
    set<int> S;
    for (int i = 1; i <= M; i++) {
        if (!S.empty()) {
            auto it = S.lower_bound(ord[i]);
            if (it != S.end()) seg.update(1, 1, M, *it, D - (arr[*it].first-arr[ord[i]].first));
            if (it == S.begin()) seg.update(1, 1, M, ord[i], 0);
            else {
                it--;
                seg.update(1, 1, M, ord[i], D - (arr[ord[i]].first-arr[*it].first));
            }
            
        }
        ll ans = seg.mx[1];
        if (ans%2) cout << ans/2 << ".5 ";
        else cout << ans/2 << " ";
        S.insert(ord[i]);
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 37020 KB Output is correct
2 Correct 123 ms 38988 KB Output is correct
3 Correct 122 ms 38856 KB Output is correct
4 Correct 111 ms 36808 KB Output is correct
5 Correct 117 ms 38084 KB Output is correct
6 Correct 122 ms 37144 KB Output is correct
7 Correct 114 ms 38080 KB Output is correct
8 Correct 105 ms 36876 KB Output is correct
9 Correct 109 ms 36724 KB Output is correct
10 Correct 117 ms 39112 KB Output is correct
11 Correct 113 ms 37660 KB Output is correct
12 Correct 123 ms 38596 KB Output is correct
13 Correct 115 ms 36884 KB Output is correct
14 Correct 118 ms 38784 KB Output is correct
15 Correct 121 ms 38600 KB Output is correct
16 Correct 111 ms 36608 KB Output is correct
17 Correct 111 ms 38112 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 37020 KB Output is correct
2 Correct 123 ms 38988 KB Output is correct
3 Correct 122 ms 38856 KB Output is correct
4 Correct 111 ms 36808 KB Output is correct
5 Correct 117 ms 38084 KB Output is correct
6 Correct 122 ms 37144 KB Output is correct
7 Correct 114 ms 38080 KB Output is correct
8 Correct 105 ms 36876 KB Output is correct
9 Correct 109 ms 36724 KB Output is correct
10 Correct 117 ms 39112 KB Output is correct
11 Correct 113 ms 37660 KB Output is correct
12 Correct 123 ms 38596 KB Output is correct
13 Correct 115 ms 36884 KB Output is correct
14 Correct 118 ms 38784 KB Output is correct
15 Correct 121 ms 38600 KB Output is correct
16 Correct 111 ms 36608 KB Output is correct
17 Correct 111 ms 38112 KB Output is correct
18 Correct 286 ms 37060 KB Output is correct
19 Correct 275 ms 39368 KB Output is correct
20 Correct 124 ms 39508 KB Output is correct
21 Correct 163 ms 37612 KB Output is correct
22 Correct 204 ms 37876 KB Output is correct
23 Correct 150 ms 37576 KB Output is correct
24 Correct 296 ms 38364 KB Output is correct
25 Correct 114 ms 37320 KB Output is correct
26 Correct 283 ms 37468 KB Output is correct
27 Correct 282 ms 39844 KB Output is correct
28 Correct 214 ms 37828 KB Output is correct
29 Correct 242 ms 39088 KB Output is correct
30 Correct 160 ms 37320 KB Output is correct
31 Correct 169 ms 39432 KB Output is correct
32 Correct 153 ms 39156 KB Output is correct
33 Correct 274 ms 37064 KB Output is correct
34 Correct 162 ms 38596 KB Output is correct