Submission #1011482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011482		bachhoangxuan	Meetings (IOI18_meetings)	C++17	100 / 100	4268 ms	586196 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
const ll inf = 1e18;

struct line{
    ll a=0,b=0,p=inf;
    line(ll a=0,ll b=0,ll p=inf):a(a),b(b),p(p){}
    bool operator<(line &o){return a>o.a;}
    bool operator<(ll k){return p<k;}
};
struct cvht{
    vector<line> x;
    cvht(){}
    ll div(ll a,ll b){
        return a/b-((a^b)<0 && a%b);
    }
    void isect(line &l,line &y){
        if(l.a==y.a) l.p=(l.b<y.b?inf:-inf);
        else l.p=div(l.b-y.b,y.a-l.a);
    }
    void add(line l){
        //cout << "add " << l.a << ' ' << l.b << ' ' << l.p << '\n';
        if(!x.empty()) isect(x.back(),l);
        while((int)x.size()>=2 && x[(int)x.size()-2].p>=x.back().p) x.pop_back(),isect(x.back(),l);
        x.push_back(l);
    }
    ll query(ll k){
        if(x.empty()) return inf;
        //cout << x.back().p << '\n';
        auto v=*lower_bound(x.begin(),x.end(),k);
        //cout << "get " << k << ' ' << v.a << ' ' << v.b << '\n';
        return v.a*k+v.b;
    }
};

std::vector<ll> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int N=(int)H.size(),Q=(int)L.size();
    vector<ll> res(Q,inf);

    vector<int> lt(N,-1),rt(N,-1),p(N,-1);
    vector<vector<int>> f(N);

    vector<int> v;
    for(int i=0;i<N;i++){
        while(!v.empty() && H[v.back()]<=H[i]) v.pop_back();
        lt[i]=(v.empty()?-1:v.back());
        v.push_back(i);
    }
    v.clear();
    for(int i=N-1;i>=0;i--){
        while(!v.empty() && H[v.back()]<H[i]) v.pop_back();
        rt[i]=(v.empty()?-1:v.back());
        v.push_back(i);
    }
    for(int i=0;i<N;i++){
        if(lt[i]==-1 || (rt[i]!=-1 && H[rt[i]]<H[lt[i]])) p[i]=rt[i];
        else p[i]=lt[i];
    }
    for(int i=0;i<N;i++) lt[i]=rt[i]=-1;
    int T=-1;
    for(int i=0;i<N;i++){
        if(p[i]==-1) T=i;
        else if(p[i]<i) rt[p[i]]=i;
        else lt[p[i]]=i;
    }
    {
        vector<pii> mx(4*N);
        function<void(int,int,int)> build = [&](int l,int r,int id){
            if(l==r){mx[id]={H[l],l};return;}
            int mid=(l+r)>>1;
            build(l,mid,id<<1);build(mid+1,r,id<<1|1);
            mx[id]=max(mx[id<<1],mx[id<<1|1]);
        };
        function<pii(int,int,int,int,int)> query = [&](int l,int r,int id,int tl,int tr){
            if(tr<l || r<tl) return make_pair(0,-1);
            if(tl<=l && r<=tr) return mx[id];
            int mid=(l+r)>>1;
            return max(query(l,mid,id<<1,tl,tr),query(mid+1,r,id<<1|1,tl,tr));
        };
        build(0,N-1,1);
        //for(int i=0;i<N;i++) cout << lt[i] << ' ' << rt[i] << '\n';
        for(int i=0;i<Q;i++){
            int u=query(0,N-1,1,L[i],R[i]).se;
            f[u].push_back(i);
            res[i]=1LL*H[u]*(R[i]-L[i]+1);
            //cout << "* " << u << ' ' << i << '\n';
        }
    }
    auto solve = [&]{
        vector<cvht> cht(4*N);
        vector<ll> total(4*N,0);
        function<void(int,int,int,int,int,ll)> update_add = [&](int l,int r,int id,int tl,int tr,ll val){
            if(tr<l || r<tl) return;
            if(tl<=l && r<=tr){
                total[id]+=val;
                return;
            }
            int mid=(l+r)>>1;
            update_add(l,mid,id<<1,tl,tr,val);update_add(mid+1,r,id<<1|1,tl,tr,val);
        };
        function<void(int,int,int,int,int,line)> update_val = [&](int l,int r,int id,int tl,int tr,line ln){
            if(tr<l || r<tl) return;
            if(tl<=l && r<=tr){
                //cout << "update " << l << ' ' << r << ' ' << id << ' ' << ln.a << ' ' << ln.b << '\n';
                ln.b-=total[id];
                cht[id].add(ln);
                return;
            }
            int mid=(l+r)>>1;
            update_val(l,mid,id<<1,tl,tr,ln);update_val(mid+1,r,id<<1|1,tl,tr,ln);
        };
        function<ll(int,int,int,int)> query = [&](int l,int r,int id,int p){
            if(l==r) return total[id]+cht[id].query(-p);
            int mid=(l+r)>>1;
            ll res=cht[id].query(-p);
            if(p<=mid) res=min(res,query(l,mid,id<<1,p));
            else res=min(res,query(mid+1,r,id<<1|1,p));
            //cout << "query " << l << ' ' << r << ' ' << id << ' ' << p << ' ' << res << ' ' << total[id] << '\n';
            return total[id]+res;
        };

        vector<ll> val(N);
        function<void(int,int,int)> dfs = [&](int l,int r,int u){
            val[u]=1LL*(r-l+1)*H[u];

            ll num=H[u];
            if(l<u){
                dfs(l,u-1,lt[u]);num+=val[lt[u]];
                val[u]=min(val[u],val[lt[u]]+1LL*(r-u+1)*H[u]);
            }
            if(u<r){
                dfs(u+1,r,rt[u]);
                val[u]=min(val[u],val[rt[u]]+1LL*(u-l+1)*H[u]);
            }
            for(int id:f[u]) res[id]=min(res[id],query(0,N-1,1,R[id])+1LL*H[u]*(u-L[id]+1));
            update_add(0,N-1,1,u,r,1LL*H[u]*(u-l+1));
            update_val(0,N-1,1,u,r,line(-H[u],num-1LL*H[u]*u,inf));
        };
        dfs(0,N-1,T);
        //cout << '*' << val[T] << '\n';
    };
    solve();
    for(int i=0;i<Q;i++) swap(L[i],R[i]),L[i]=N-1-L[i],R[i]=N-1-R[i];
    reverse(H.begin(),H.end());
    reverse(f.begin(),f.end());
    reverse(lt.begin(),lt.end());
    reverse(rt.begin(),rt.end());
    T=N-1-T;
    //cout << T << '\n';
    for(int i=0;i<N;i++){
        swap(lt[i],rt[i]);
        if(lt[i]!=-1) lt[i]=N-1-lt[i];
        if(rt[i]!=-1) rt[i]=N-1-rt[i];
        //cout << lt[i] << ' ' << rt[i] << '\n';
    }
    solve();
    return res;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40