Submission #700218

#	Time	Username	Problem	Language	Result	Execution time	Memory
700218		Lobo	Measures (CEOI22_measures)	C++17	100 / 100	505 ms	28332 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 4e5+10;

int n, m, d;
int trmn[4*maxn], trmx[4*maxn], lzmn[4*maxn], lzmx[4*maxn];

void flush(int no, int l, int r) {
    trmn[no]+= lzmn[no];
    trmx[no]+= lzmx[no];

    if(l != r) {
        int lc=2*no,rc=2*no+1;
        lzmn[lc]+= lzmn[no];
        lzmn[rc]+= lzmn[no];

        lzmx[lc]+= lzmx[no];
        lzmx[rc]+= lzmx[no];
    }
    lzmn[no] = 0;
    lzmx[no] = 0;
}

void updmn(int no, int l, int r, int L, int R, int val) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lzmn[no] = val;
        flush(no,l,r);
        return;
    }

    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    updmn(lc,l,mid,L,R,val);
    updmn(rc,mid+1,r,L,R,val);
    trmn[no] = min(trmn[lc],trmn[rc]);
}
void updmx(int no, int l, int r, int L, int R, int val) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lzmx[no] = val;
        flush(no,l,r);
        return;
    }

    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    updmx(lc,l,mid,L,R,val);
    updmx(rc,mid+1,r,L,R,val);
    trmx[no] = max(trmx[lc],trmx[rc]);
}

int qrymn(int no, int l, int r, int L, int R) {
    flush(no,l,r);
    if(l > R || r < L) return inf;
    if(l >= L && r <= R) return trmn[no];
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    return min(qrymn(lc,l,mid,L,R),qrymn(rc,mid+1,r,L,R));
}

int qrymx(int no, int l, int r, int L, int R) {
    flush(no,l,r);
    if(l > R || r < L) return -inf;
    if(l >= L && r <= R) return trmx[no];
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    return max(qrymx(lc,l,mid,L,R),qrymx(rc,mid+1,r,L,R));
}

void solve() {
    cin >> n >> m >> d;
    int ans = 0;
    vector<pair<int,int>> qr,cc;
    for(int i = 1; i <= n+m; i++) {
        int x; cin >> x;
        qr.pb(mp(x,i));
        cc.pb(mp(x,i));
    }
    sort(all(cc));
    updmx(1,1,n+m,1,n+m,-inf);
    updmn(1,1,n+m,1,n+m,+inf);
    for(int i = 1; i <= n+m; i++) {
        int x = qr[i-1].fr;
        int id = upper_bound(all(cc),mp(x,i))-cc.begin();
        updmx(1,1,n+m,id,id,+inf+x);
        updmn(1,1,n+m,id,id,-inf+x);
        updmx(1,1,n+m,id,n+m,-d);
        updmn(1,1,n+m,id,n+m,-d);
        ans = max(ans, -qrymn(1,1,n+m,id,n+m)+qrymx(1,1,n+m,1,id));

        if(i > n) {
            cout << ans/2;
            if(ans%2 == 1) cout << ".5 ";
            else cout << " ";
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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