Submission #1304415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304415		AMnu	Measures (CEOI22_measures)	C++20	0 / 100	161 ms	25464 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

const int MAXN = 2e5+5;
const ll INF = 1e15;

int N, M, D, P[MAXN];
pii A[MAXN];

struct seg {
    ll ans=0, mn=INF, mx=-INF, lz=0;
    int cnt=0;
}
tre[MAXN*4];

seg join(seg x,seg y) {
    seg z;
    if (x.cnt == 0) return y;
    if (y.cnt == 0) return x;
    z.cnt = x.cnt+y.cnt;
    z.mn = min(x.mn,y.mn);
    z.mx = max(x.mx,y.mx);
    z.ans = max(x.ans,y.ans);
    if (x.cnt > 0 && y.cnt > 0) {
        z.ans = max(x.mx-y.mn,z.ans);
    }
    return z;
}

void debug(int id=1,int l=1,int r=N+M) {
    cout << l << " " << r << " " << tre[id].ans << " " << tre[id].mn << " " << tre[id].mx << "\n";
    if (l == r) return;
    int m = (l+r)/2;
    debug(id*2,l,m);
    debug(id*2+1,m+1,r);
}

int query(int x,int id=1,int l=1,int r=N+M) {
    if (l > x) return 0;
    if (r <= x) return tre[id].cnt;
    int m = (l+r)/2;
    return query(x,id*2,l,m)+query(x,id*2+1,m+1,r);
}

void down(int id) {
    if (tre[id].lz == 0) return;
    if (tre[id*2].cnt > 0) {
        tre[id*2].mn -= tre[id].lz;
        tre[id*2].mx -= tre[id].lz;
    }
    if (tre[id*2+1].cnt > 0) {
        tre[id*2+1].mn -= tre[id].lz;
        tre[id*2+1].mx -= tre[id].lz;
    }
    tre[id].lz = 0;
}

void update(int x,int id=1,int l=1,int r=N+M) {
    if (tre[id].cnt == 0) return;
    if (r < x) return;
    if (l >= x) {
        tre[id].mn -= D;
        tre[id].mx -= D;
        tre[id].lz += D;
        return;
    }
    down(id);
    int m = (l+r)/2;
    update(x,id*2,l,m);
    update(x,id*2+1,m+1,r);
    tre[id] = join(tre[id*2],tre[id*2+1]);
}

void add(int x,ll y,int id=1,int l=1,int r=N+M) {
    if (l == r) {
        tre[id].mn = y;
        tre[id].mx = y;
        tre[id].cnt++;
        return;
    }
    down(id);
    int m = (l+r)/2;
    if (x <= m) {
        add(x,y,id*2,l,m);
    }
    else {
        add(x,y,id*2+1,m+1,r);
    }
    tre[id] = join(tre[id*2],tre[id*2+1]);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M >> D;
    for (int i=1;i<=N+M;i++) {
        cin >> A[i].fi;
        A[i].se = i;
    }
    sort(A+1,A+N+M+1);
    for (int i=1;i<=N+M;i++) {
        P[A[i].se] = i;
    }
    for (int i=1;i<=N+M;i++) {
        int x = query(P[i]-1);
        // cout << "\nx = " << A[P[i]].fi-x*D << "\n";
        add(P[i],A[P[i]].fi-x*D);
        update(P[i]+1);
        // debug();
        if (i <= N) continue;
        cout << tre[1].ans/2;
        if (tre[1].ans % 2 == 1) {
            cout << ".5";
        }
        cout << " ";
    }
}

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