oj.uz

답안 #657201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657201 2022-11-09T06:20:47 Z dooompy Measures (CEOI22_measures) C++17
86 / 100
 176 ms 40356 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll 

ll pos[200005];
ll val[200005];

struct node {
    ll mn, mx, lz, ans;
};

node tree[200005 * 4];

void sett(int x, int l, int r, int p, int v) {
    if (l == r) {
        tree[x].mn = tree[x].mx = v + tree[x].lz;
        tree[x].ans = 0;
        return;
    }

    int mid = (l + r) / 2;

    if (p <= mid) sett(2 * x, l, mid, p, v);
    else sett(2 * x + 1, mid + 1, r, p, v);

    tree[x].mn = tree[x].lz + min(tree[2 * x].mn, tree[2 * x + 1].mn);
    tree[x].mx = tree[x].lz + max(tree[2 * x].mx, tree[2 * x + 1].mx);
    tree[x].ans = max({tree[2 * x].ans, tree[2 * x + 1].ans, tree[2 * x].mx - tree[2 * x + 1].mn});
}

void add(int x, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        tree[x].lz += v;
        tree[x].mx += v;
        tree[x].mn += v;
        return;
    }

    if (l > qr || ql > r) return;

    int mid = (l + r) / 2;

    add(2 * x, l, mid, ql, qr, v);
    add(2 * x + 1, mid + 1, r, ql, qr, v);

    tree[x].mn = tree[x].lz + min(tree[2 * x].mn, tree[2 * x + 1].mn);
    tree[x].mx = tree[x].lz + max(tree[2 * x].mx, tree[2 * x + 1].mx);
    tree[x].ans = max({tree[2 * x].ans, tree[2 * x + 1].ans, tree[2 * x].mx - tree[2 * x + 1].mn});
}

void build(int x, int l, int r) {
    tree[x].mn = 1e15;
    tree[x].mx = -1e15;
    tree[x].ans = -1e15;


    if (l == r) {
        return;
    }

    int mid = (l + r) / 2;

    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m, d; cin >> n >> m >> d;

    build(1, 1, 200000);
    vector<pair<ll, ll>> v;
    for (int i = 1; i <= n + m; i++) {
        int t; cin >> t;
        val[i] = t;
        v.push_back({t, i});
    }

    sort(v.begin(), v.end());

    for (int i = 1; i <= n + m; i++) {
        pos[v[i - 1].second] = i;
    }

    for (int i = 1; i <= n; i++) {
        sett(1, 1, 200000, pos[i], val[i]);
        add(1, 1, 200000, pos[i] + 1, 200000, -d);
    }

    for (int i = n + 1; i <= n + m; i++) {
        sett(1, 1, 200000, pos[i], val[i]);
        add(1, 1, 200000, pos[i] + 1, 200000, -d);

        ll res = tree[1].ans;

        if (res % 2 == 1) {
            cout << res / 2  <<  ".5 ";
        } else cout << res / 2 << " " ;
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 16764 KB Output is correct
2 Correct 8 ms 16852 KB Output is correct
3 Correct 8 ms 16832 KB Output is correct
4 Correct 8 ms 16852 KB Output is correct
5 Correct 8 ms 16820 KB Output is correct
6 Correct 8 ms 16780 KB Output is correct
7 Correct 8 ms 16852 KB Output is correct
8 Correct 8 ms 16852 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 16764 KB Output is correct
2 Correct 8 ms 16852 KB Output is correct
3 Correct 8 ms 16832 KB Output is correct
4 Correct 8 ms 16852 KB Output is correct
5 Correct 8 ms 16820 KB Output is correct
6 Correct 8 ms 16780 KB Output is correct
7 Correct 8 ms 16852 KB Output is correct
8 Correct 8 ms 16852 KB Output is correct
9 Runtime error 166 ms 40356 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 24164 KB Output is correct
2 Correct 122 ms 26104 KB Output is correct
3 Correct 121 ms 25968 KB Output is correct
4 Correct 111 ms 23860 KB Output is correct
5 Correct 120 ms 25172 KB Output is correct
6 Correct 111 ms 24216 KB Output is correct
7 Correct 121 ms 25204 KB Output is correct
8 Correct 119 ms 23880 KB Output is correct
9 Correct 118 ms 23884 KB Output is correct
10 Correct 119 ms 26296 KB Output is correct
11 Correct 116 ms 24632 KB Output is correct
12 Correct 118 ms 25704 KB Output is correct
13 Correct 109 ms 23860 KB Output is correct
14 Correct 123 ms 25772 KB Output is correct
15 Correct 117 ms 25660 KB Output is correct
16 Correct 108 ms 23864 KB Output is correct
17 Correct 115 ms 25144 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 24164 KB Output is correct
2 Correct 122 ms 26104 KB Output is correct
3 Correct 121 ms 25968 KB Output is correct
4 Correct 111 ms 23860 KB Output is correct
5 Correct 120 ms 25172 KB Output is correct
6 Correct 111 ms 24216 KB Output is correct
7 Correct 121 ms 25204 KB Output is correct
8 Correct 119 ms 23880 KB Output is correct
9 Correct 118 ms 23884 KB Output is correct
10 Correct 119 ms 26296 KB Output is correct
11 Correct 116 ms 24632 KB Output is correct
12 Correct 118 ms 25704 KB Output is correct
13 Correct 109 ms 23860 KB Output is correct
14 Correct 123 ms 25772 KB Output is correct
15 Correct 117 ms 25660 KB Output is correct
16 Correct 108 ms 23864 KB Output is correct
17 Correct 115 ms 25144 KB Output is correct
18 Correct 164 ms 24308 KB Output is correct
19 Correct 176 ms 26008 KB Output is correct
20 Correct 121 ms 25952 KB Output is correct
21 Correct 145 ms 24060 KB Output is correct
22 Correct 145 ms 24504 KB Output is correct
23 Correct 125 ms 24248 KB Output is correct
24 Correct 166 ms 24784 KB Output is correct
25 Correct 112 ms 23884 KB Output is correct
26 Correct 163 ms 23860 KB Output is correct
27 Correct 176 ms 26324 KB Output is correct
28 Correct 153 ms 24340 KB Output is correct
29 Correct 159 ms 25688 KB Output is correct
30 Correct 139 ms 23760 KB Output is correct
31 Correct 148 ms 25852 KB Output is correct
32 Correct 125 ms 25648 KB Output is correct
33 Correct 162 ms 23864 KB Output is correct
34 Correct 148 ms 25172 KB Output is correct