Submission #696353

#	Time	Username	Problem	Language	Result	Execution time	Memory
696353		ParsaS	Measures (CEOI22_measures)	C++17	100 / 100	453 ms	39172 KiB

Main

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
#define int ll
const int N = 4e5 + 5;
int n, m, a[N], D, tmp;
ll mx[N << 2], lz[N << 2], mn[N << 2];
int fen[N];
bool mark[N];

void upd_fen(int i) {
    for (++i; i <= tmp + 2; i += i & -i)
        fen[i]++;
}
int query_fen(int i) {
    int res = 0;
    for (++i; i > 0; i -= i & -i)
        res += fen[i];
    return res;
}
void shift(int v, int tl, int tr) {
    mx[v] += lz[v];
    mn[v] += lz[v];
    if (tl < tr) {
        lz[v << 1] += lz[v];
        lz[v << 1 | 1] += lz[v];
    }
    lz[v] = 0;
}
void upd(int l, int r, ll val, int v = 1, int tl = 0, int tr = tmp) {
    shift(v, tl, tr);
    if (l > tr || r < tl)
        return;
    if (tl >= l && tr <= r) {
        lz[v] += val;
        shift(v, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, val, v << 1, tl, mid);
    upd(l, r, val, v << 1 | 1, mid + 1, tr);
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
}
void set_val(int i, ll val, int v = 1, int tl = 0, int tr = tmp) {
    shift(v, tl, tr);
    if (tl ==tr) {
        mx[v] = mn[v] = val;
        return;
    }
    int mid = (tl + tr) >> 1;
    if (i <= mid) {
        set_val(i, val, v << 1, tl, mid);
    }
    else {
        set_val(i, val, v << 1 | 1, mid + 1, tr);
    }
	shift(v << 1, tl, mid);
	shift(v << 1 | 1, mid + 1, tr);
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
}
pair<ll, ll> query(int l, int r, int v = 1, int tl = 0, int tr = tmp) {
    pair<ll, ll> out(-1e17, 1e17);
    if (l > tr || r < tl)
        return out;
    if (tl >= l && tr <= r)
        return mp(mx[v], mn[v]);
    int mid = (tl + tr) >> 1;
    pair<ll, ll> lc = query(l, r, v << 1, tl, mid);
    pair<ll, ll> rc = query(l, r, v << 1 | 1, mid + 1, tr);
    return mp(max(lc.fi, rc.fi), min(lc.se, rc.se));
}
void solve() {
    cin >> n >> m >> D;
    ll ans = 0;
    vector<pair<int, int> > vec;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vec.pb(mp(a[i], tmp));
        tmp++;
    }
    for (int i = 0; i < m; i++) {
        cin >> a[tmp];
        vec.pb(mp(a[tmp], tmp));
        tmp++;
    }
    sort(vec.begin(), vec.end());
    memset(mx, -63, sizeof mx);
    memset(mn, 63, sizeof mn);
    for (int i = 0; i < tmp; i++) {
        int j = lower_bound(vec.begin(), vec.end(), mp(a[i], i)) - vec.begin();
        ll x = 1LL * D * query_fen(j) - a[i];
        upd_fen(j);
        upd(j + 1, tmp, D);
        set_val(j, x);
        ans = max(ans, query(j, tmp).fi - query(0, j).se);

        if (i >= n) {
            cout << ans / 2;
            if (ans % 2)
                cout << ".5";
            if (i < tmp - 1)
                cout << ' ';
        }
    }
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

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