Submission #1118141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118141		Zero_OP	Measures (CEOI22_measures)	C++14	100 / 100	420 ms	38232 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41