oj.uz

Submission #1118141

# Submission time Handle Problem Language Result Execution time Memory
1118141 2024-11-25T03:48:27 Z Zero_OP Measures (CEOI22_measures) C++14
100 / 100
 420 ms 38232 KB 
#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

struct fenwick_tree{
    vector<int> bit;
    fenwick_tree(int n) : bit(n + 1, 0) {}

    void update(int i, int v){
        ++i;
        for(; i < (int)bit.size(); i += i & (-i)) bit[i] += v;
    }

    int query(int i){
        int sum = 0;
        ++i;
        for(; i > 0; i -= i & (-i)) sum += bit[i];
        return sum;
    }
};

const long long inf = 1e18;

struct segment_tree{
    vector<long long> info_min, info_max, lazy_tag;
    segment_tree(int n) : info_min(n << 2), info_max(n << 2), lazy_tag(n << 2) {}

    void build(int id, int l, int r){
        if(l == r){
            info_min[id] = inf;
            info_max[id] = -inf;
        } else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            info_min[id] = min(info_min[id << 1], info_min[id << 1 | 1]);
            info_max[id] = max(info_max[id << 1], info_max[id << 1 | 1]);
        }
    }

    void apply_sum(int id, long long tag){
        info_min[id] += tag;
        info_max[id] += tag;
        lazy_tag[id] += tag;
    }

    void lazy_down(int id){
        if(lazy_tag[id] != 0){
            apply_sum(id << 1, lazy_tag[id]);
            apply_sum(id << 1 | 1, lazy_tag[id]);
            lazy_tag[id] = 0;
        }
    }

    void change_position(int id, int l, int r, int pos, long long val){
        if(l == r) info_min[id] = info_max[id] = val;
        else{
            int mid = l + r >> 1;
            lazy_down(id);
            if(pos <= mid) change_position(id << 1, l, mid, pos, val);
            else change_position(id << 1 | 1, mid + 1, r, pos, val);

            info_min[id] = min(info_min[id << 1], info_min[id << 1 | 1]);
            info_max[id] = max(info_max[id << 1], info_max[id << 1 | 1]);
        }
    }

    void update(int id, int l, int r, int u, int v, long long val){
        if(u <= l && r <= v) apply_sum(id, val);
        else{
            int mid = l + r >> 1;
            lazy_down(id);
            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);

            info_min[id] = min(info_min[id << 1], info_min[id << 1 | 1]);
            info_max[id] = max(info_max[id << 1], info_max[id << 1 | 1]);
        }
    }

    long long query_min(int id, int l, int r, int u, int v){
        if(u <= l && r <= v) return info_min[id];
        int mid = l + r >> 1;
        lazy_down(id);
        if(u > mid) return query_min(id << 1 | 1, mid + 1, r, u, v);
        if(mid >= v) return query_min(id << 1, l, mid, u, v);
        return min(query_min(id << 1, l, mid, u, v), query_min(id << 1 | 1, mid + 1, r, u, v));
    }

    long long query_max(int id, int l, int r, int u, int v){
        if(u <= l && r <= v) return info_max[id];
        int mid = l + r >> 1;
        lazy_down(id);
        if(u > mid) return query_max(id << 1 | 1, mid + 1, r, u, v);
        if(mid >= v) return query_max(id << 1, l, mid, u, v);
        return max(query_max(id << 1, l, mid, u, v), query_max(id << 1 | 1, mid + 1, r, u, v));
    }

};

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, M;
    long long D;
    cin >> N >> M >> D;

    vector<long long> a(N), b(M), all;
    for(int i = 0; i < N; ++i){
        cin >> a[i];
        all.emplace_back(a[i]);
    }

    for(int i = 0; i < M; ++i){
        cin >> b[i];
        all.emplace_back(b[i]);
    }

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

    set<pair<int, int>> online;
    for(int i = 0; i < (int)all.size(); ++i){
        online.insert({all[i], i});
    }

    int sz = N + M;
    segment_tree tr(sz); tr.build(1, 0, sz - 1);
    fenwick_tree ft(sz);

    long long ans = 0;
    auto insert_data = [&](int x){ //maximum D * (j - i) - (a[j] - a[i])
        auto it = online.lower_bound({x, 0});
        assert(it != online.end());

        int pos = it -> second;
        online.erase(it);

        int exact = ft.query(pos);
        tr.change_position(1, 0, sz - 1, pos, 1LL * exact * D - x);
        tr.update(1, 0, sz - 1, pos, sz - 1, D);
        ft.update(pos, +1);

        long long low = tr.query_min(1, 0, sz - 1, 0, pos);
        long long high = tr.query_max(1, 0, sz - 1, pos, sz - 1);
        ans = max(ans, high - low);
    };

    for(int i = 0; i < N; ++i){
        insert_data(a[i]);
    }

    for(int i = 0; i < M; ++i){
        insert_data(b[i]);
        cout << (ans >> 1) << (ans & 1 ? ".5" : "") << ' ';
    }

    return 0;
}

Compilation message

Main.cpp: In member function 'void segment_tree::build(int, int, int)':
Main.cpp:35:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |             int mid = l + r >> 1;
      |                       ~~^~~
Main.cpp: In member function 'void segment_tree::change_position(int, int, int, int, long long int)':
Main.cpp:60:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |             int mid = l + r >> 1;
      |                       ~~^~~
Main.cpp: In member function 'void segment_tree::update(int, int, int, int, int, long long int)':
Main.cpp:73:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |             int mid = l + r >> 1;
      |                       ~~^~~
Main.cpp: In member function 'long long int segment_tree::query_min(int, int, int, int, int)':
Main.cpp:85:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'long long int segment_tree::query_max(int, int, int, int, int)':
Main.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 608 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 608 KB Output is correct
9 Correct 351 ms 33064 KB Output is correct
10 Correct 329 ms 32972 KB Output is correct
11 Correct 180 ms 32900 KB Output is correct
12 Correct 226 ms 32972 KB Output is correct
13 Correct 201 ms 32972 KB Output is correct
14 Correct 199 ms 32972 KB Output is correct
15 Correct 363 ms 32972 KB Output is correct
16 Correct 185 ms 32852 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 35520 KB Output is correct
2 Correct 201 ms 37940 KB Output is correct
3 Correct 209 ms 37836 KB Output is correct
4 Correct 216 ms 35776 KB Output is correct
5 Correct 202 ms 37064 KB Output is correct
6 Correct 189 ms 36032 KB Output is correct
7 Correct 208 ms 37056 KB Output is correct
8 Correct 200 ms 35776 KB Output is correct
9 Correct 186 ms 35504 KB Output is correct
10 Correct 199 ms 38100 KB Output is correct
11 Correct 223 ms 36560 KB Output is correct
12 Correct 218 ms 37380 KB Output is correct
13 Correct 207 ms 35584 KB Output is correct
14 Correct 213 ms 37580 KB Output is correct
15 Correct 188 ms 37328 KB Output is correct
16 Correct 219 ms 35276 KB Output is correct
17 Correct 200 ms 37080 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 35520 KB Output is correct
2 Correct 201 ms 37940 KB Output is correct
3 Correct 209 ms 37836 KB Output is correct
4 Correct 216 ms 35776 KB Output is correct
5 Correct 202 ms 37064 KB Output is correct
6 Correct 189 ms 36032 KB Output is correct
7 Correct 208 ms 37056 KB Output is correct
8 Correct 200 ms 35776 KB Output is correct
9 Correct 186 ms 35504 KB Output is correct
10 Correct 199 ms 38100 KB Output is correct
11 Correct 223 ms 36560 KB Output is correct
12 Correct 218 ms 37380 KB Output is correct
13 Correct 207 ms 35584 KB Output is correct
14 Correct 213 ms 37580 KB Output is correct
15 Correct 188 ms 37328 KB Output is correct
16 Correct 219 ms 35276 KB Output is correct
17 Correct 200 ms 37080 KB Output is correct
18 Correct 355 ms 36180 KB Output is correct
19 Correct 338 ms 37836 KB Output is correct
20 Correct 209 ms 37840 KB Output is correct
21 Correct 248 ms 35848 KB Output is correct
22 Correct 276 ms 36144 KB Output is correct
23 Correct 252 ms 36040 KB Output is correct
24 Correct 420 ms 36584 KB Output is correct
25 Correct 207 ms 35668 KB Output is correct
26 Correct 340 ms 35516 KB Output is correct
27 Correct 385 ms 38232 KB Output is correct
28 Correct 292 ms 36044 KB Output is correct
29 Correct 304 ms 37324 KB Output is correct
30 Correct 242 ms 35536 KB Output is correct
31 Correct 256 ms 37584 KB Output is correct
32 Correct 231 ms 37400 KB Output is correct
33 Correct 330 ms 35284 KB Output is correct
34 Correct 255 ms 37128 KB Output is correct