Submission #696064

#	Time	Username	Problem	Language	Result	Execution time	Memory
696064		ParsaS	Measures (CEOI22_measures)	C++17	0 / 100	1563 ms	40392 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 seg[2][N << 2], lz[2][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 t, int v, int tl, int tr) {
    seg[t][v] += lz[t][v];
    if (tl < tr) {
        lz[t][v << 1] += lz[t][v];
        lz[t][v << 1 | 1] += lz[t][v];
    }
    lz[t][v] = 0;
}

void upd(int t, int l, int r, ll val, int v = 1, int tl = 0, int tr = tmp) {
    shift(t, v, tl, tr);
    if (l > tr || r < tl)
        return;
    if (tl >= l && tr <= r) {
        lz[t][v] += val;
        shift(t, v, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    upd(t, l, r, val, v << 1, tl, mid);
    upd(t, l, r, val, v << 1 | 1, mid + 1, tr);
    if (t) {
        seg[t][v] = min(seg[t][v << 1], seg[t][v << 1 | 1]);
    }
    else {
        seg[t][v] = max(seg[t][v << 1], seg[t][v << 1 | 1]);
    }
}
ll query(int t, int l, int r, int v = 1, int tl = 0, int tr = tmp) {
    shift(t, v, tl, tr);
    if (l > tr || r < tl) {
        return t ? 1e17 : -1e17;
    }
    if (tl >= l && tr <= r)
        return seg[t][v];
    int mid = (tl + tr) >> 1;
    ll lc = query(t, l, r, v << 1, tl, mid), rc = query(t, l, r, v << 1 | 1, mid + 1, tr);
    if (t)
        return min(lc, rc);
    return max(lc, rc);
}

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());
    fill(seg[0], seg[0] + (N << 2), -1e17);
    fill(seg[1], seg[1] + (N << 2), 1e17);
    for (int i = 0; i < tmp; i++) {
        int j = lower_bound(vec.begin(), vec.end(), mp(a[i], i)) - vec.begin();
        mark[j] = true;
        ll x = 1LL * D * query_fen(j) - a[i];
        upd_fen(j);
        upd(0, j + 1, tmp, D);
        upd(1, j + 1, tmp, D);
        upd(0, j, j, x - query(0, j, j));
        upd(1, j, j, x - query(1, j, j));

        //ans = max(ans, query(0, j, tmp) - query(1, 0, j));

        if (i >= n) {
            ans = 0;
            for (int j = 0; j < tmp; j++)
                ans = max(ans, query(0, j, tmp) - query(1, 0, j));
            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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41