Submission #1143426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143426		imarn	Measures (CEOI22_measures)	C++20	0 / 100	132 ms	28896 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=4e5+5;
vector<int>v;
multiset<int>ms;
struct node{
    ll mxl,mxr,mx,tt;
    node operator+(node b){
        return node{max(mxl,tt+b.mxl),max(b.mxr,b.tt+mxr),max({mx,b.mx,mxr+b.mxl}),tt+b.tt};
    }
}t[4*mxn];

void update(int i,int l,int r,int id,int amt){
    if(r<id||l>id)return;
    if(l==r)return void(t[i]=node{max(1ll*0,amt+t[i].mxl),max(1ll*0,amt+t[i].mxr),max(1ll*0,amt+t[i].mx),amt+t[i].tt});
    int m=(l+r)>>1;
    update(2*i,l,m,id,amt);update(2*i+1,m+1,r,id,amt);
    t[i]=t[2*i]+t[2*i+1];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,d;cin>>n>>m>>d;int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];v.pb(a[i]);
    }int b[m];
    for(int i=0;i<m;i++)cin>>b[i],v.pb(b[i]);
    sort(all(v));v.erase(unique(all(v)),v.end());int sz=v.size();
    for(int i=0;i<n;i++){
        ms.insert(a[i]);
        auto it = ms.lower_bound(a[i]);
        if(it!=ms.begin()){
            update(1,1,sz,ub(v,b[i]),d-(a[i]-*prev(it)));
        }
        if(it!=(--ms.end())){
            if(it!=ms.begin())update(1,1,sz,ub(v,*next(it)),-d+(b[i]-*prev(it)));
            update(1,1,sz,ub(v,*next(it)),d-(*next(it)-a[i]));
        }
    }
    for(int i=0;i<m;i++){
        ms.insert(b[i]);
        auto it = ms.lower_bound(b[i]);
        if(it!=ms.begin()){
            update(1,1,sz,ub(v,b[i]),d-(b[i]-*prev(it)));
        }
        if(it!=(--ms.end())){
            if(it!=ms.begin())update(1,1,sz,ub(v,*next(it)),-d+(b[i]-*prev(it)));
            update(1,1,sz,ub(v,*next(it)),d-(*next(it)-b[i]));
        }ll rs=t[1].mx;
        if(rs&1)cout<<rs/2<<".5 ";
        else cout<<rs/2<<' ';
    }

}

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