Submission #1036309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036309		underwaterkillerwhale	Measures (CEOI22_measures)	C++17	100 / 100	382 ms	31804 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 240;
const ll  INF = 1e18;
const int BASE = 137;

int n, m;
ll D;
ll b[2 * N];
vector<ll> vals;

struct Segment_Tree {
    struct Node {
        ll mx, mn, cnt;
    };
    int m;
    Node st[N << 3];
    ll lz[N << 3];
    void init (int n) {
        m = n;
        rep (i, 1, n << 2) st[i].mx = -INF, st[i].mn = INF, st[i].cnt = 0;
    }

    Node mer (Node lf, Node rt) {
        return {max(lf.mx, rt.mx), min(lf.mn, rt.mn), lf.cnt + rt.cnt};
    }

    void down (int id){
        rep (i, id << 1, id << 1 | 1) {
            lz[i] += lz[id];
            st[i].mn += lz[id];
            st[i].mx += lz[id];
        }
        lz[id] = 0;
    }

    void update (int id, int l, int r, int pos, ll val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id].mx = max(st[id].mx, val);
            st[id].mn = min(st[id].mn, val);
            st[id].cnt++;
            return;
        }
        int mid = l + r >> 1;
        down(id);
        update (id << 1, l, mid, pos, val);
        update (id << 1 | 1, mid + 1, r, pos, val);
        st[id] = mer(st[id << 1], st[id << 1 | 1]);
    }

    void update (int id, int l, int r, int u, int v, ll val){
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            st[id].mx += val;
            st[id].mn += val;
            lz[id] += val;
            return;
        }
        int mid = l + r >> 1;
        down(id);
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = mer(st[id << 1], st[id << 1 | 1]);
    }

    Node get (int id, int l, int r, int u, int v){
        if (l > v || r < u) return {-INF, INF, 0};
        if (l >= u && r <= v) return st[id];
        int mid = l + r >> 1;
        down(id);
        return mer(get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
    }

    void update (int pos, ll val) {
        update (1, 1, m, pos, val);
    }

    void update (int u, int v, ll val) {
        update (1, 1, m, u, v, val);
    }

    Node get (int u, int v) {
        return get (1, 1, m, u, v);
    }
}ST;

void solution (){
    cin >> n >> m >> D;
    m += n;
    rep (i, 1, m) cin >> b[i], vals.push_back(b[i]);
    sort (ALL(vals));
    ll K; vals.resize(K = unique(ALL(vals)) - vals.begin());
    ST.init(K);
    ll res = 0;
    rep (i, 1, m) {
        int pos = lower_bound(ALL(vals), b[i]) - vals.begin() + 1;
        ST.update (pos, (ST.get(1, pos).cnt + 1) * D - b[i]);
        ST.update (pos + 1, K, D);
        res = max (res, ST.get(pos, K).mx - ST.get(1, pos).mn);
        if (i > n) {
            if (res % 2 == 0)
            cout << res / 2 <<" ";
            else cout << fixed <<setprecision(1) <<1.0 * res / 2 <<" ";
        }
    }
}

#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);
/*
*/
int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
no bug challenge +1

*/

Compilation message (stderr)

Main.cpp: In member function 'void Segment_Tree::update(int, int, int, int, long long int)':
Main.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, long long int)':
Main.cpp:79:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'Segment_Tree::Node Segment_Tree::get(int, int, int, int, int)':
Main.cpp:89:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41