Submission #1022843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022843		hotboy2703	Meetings (IOI18_meetings)	C++17	100 / 100	1701 ms	353788 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
ll n,q;
const ll MAXN = 7.5e5+100;
const ll MAXK = 20;
const ll INF = 1e18;
int sp[MAXK][MAXN];
vector <ll> res;
pll all_queries[MAXN];
vector <pair <pll,ll> > questions[MAXN];
ll a[MAXN];
struct line{
    mutable ll a,b;
    ll r;
    ll eval(ll x,ll lazy)const {
        return a * x + b + lazy;
    }
    bool operator < (const line &p)const{
        return r < p.r;
    }bool operator < (const ll &p)const{
        return r < p;
    }
};
ll max_id(ll l,ll r){
    ll sz = __lg(r-l+1);
    ll L = sp[sz][l],R = sp[sz][r-MASK(sz)+1];
    if (a[R] > a[L])return R;
    else return L;
}
ll intersect(line i,line j,ll lazy){
    j.b+=lazy;
    if (j.a==i.a)return i.b>j.b?-INF:INF;
    return (i.b-j.b)/(j.a-i.a);
}
set <line,less<>> s;
void dfs(ll l,ll r,set<line>::iterator &is,set <line>::iterator &ie,ll &lazy){
    if (l > r){is = s.end(),ie = s.end(),lazy = 0;return;}
    if (l==r){
        is = ie = s.insert({0,a[l],l}).fi;
        lazy = 0;
    }
    else{
        ll mid = max_id(l,r);
        set<line>::iterator Lb,Lf,Rb,Rf;
        ll wL=0,wR=0;
        if (mid == l){
            dfs(mid+1,r,Rf,Rb,wR);
            wR += (mid-l+1)*a[mid];
            lazy = wR;
            is = s.insert({0,a[mid]-lazy,mid}).fi;
            ie = Rb;
        }
        else if (mid==r){
            dfs(l,mid-1,Lf,Lb,wL);
            lazy = wL;
            is = Lf;
            ie = s.insert({0,(*Lb).eval(mid-1,wL)+ a[mid]-lazy,mid}).fi;
        }
        else{
        //    cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;

            dfs(l,mid-1,Lf,Lb,wL);
            dfs(mid+1,r,Rf,Rb,wR);
            wR += (mid-l+1)*a[mid];
            line T;
            T.a = a[mid];
            T.b = a[mid] * (-l+1);
            T.r = mid;
            if (mid != l)T.b = (*Lb).eval(mid-1,wL) + a[mid] - a[mid] * mid;
            while (Rf!=s.end()&&intersect(T,*Rf,wR) >= (*Rf).r){
                T.r = (*Rf).r;
                Rf = s.erase(Rf);
            }
            if (Rf != s.end()){
                T.r = max(T.r,intersect(T,*Rf,wR));
            }
//            cout<<"TTT "<<l<<' '<<r<<' '<<mid<<endl;
//            if (mid>l)cout<<"T "<<T.a<<' '<<T.b<<' '<<(*Lb).eval(mid-1,wL) + a[mid] - a[mid] * mid<<endl;
            if (mid-l+1>r-mid){

                lazy = wL;
                auto itmid = s.insert({T.a,T.b - lazy,T.r}).fi;
                is = (mid > l ? Lf : itmid);
                for (auto it = Rf;it != s.end();it ++){
                    (*it).b += wR-lazy;
                }
            }
            else{
                lazy = wR;
                auto itmid = s.insert({T.a,T.b - lazy,T.r}).fi;
                is = (mid > l ? Lf : itmid);
                for (auto it = Lf;it != itmid;it ++){
                    (*it).b += wL-lazy;
                }
            }
            ie = prev(s.end());

        }
//            cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
//            for (auto it = is;it != s.end();it++){
//                line x = *it;
//                cout<<x.a<<' '<<x.b+lazy<<' '<<x.r<<endl;
//            }
    }
    while (!questions[l].empty() && questions[l].back().fi.fi <= r){
        ll id = questions[l].back().fi.se;
        ll pre = questions[l].back().se;
        ll y = questions[l].back().fi.fi;
        res[id] = min(res[id],pre + ((*s.lower_bound(y)).eval(y,lazy)));
        questions[l].pop_back();
    }
}
void solve(){
    for (ll i = 0;i < n;i ++)sp[0][i] = i;
    for (ll j = 1;j < MAXK;j ++){
        for (ll i = 0;i + MASK(j) - 1 < n;i ++){
            if (a[sp[j-1][i+MASK(j-1)]] > a[sp[j-1][i]])sp[j][i] = sp[j-1][i+MASK(j-1)];
            else sp[j][i] = sp[j-1][i];
        }
    }
    for (ll i = 0;i < n;i ++)questions[i].clear();
    for (ll i = 0;i < q;i ++){
        ll l = all_queries[i].fi,r = all_queries[i].se;
        ll mid = max_id(l,r);
        if (mid < r)questions[mid+1].push_back(MP(MP(r,i),a[mid] * (mid-l+1)));
        res[i] = min(res[i],a[mid]*(r-l+1));
    }
    for (ll i = 0;i < n;i ++){
        sort(questions[i].begin(),questions[i].end(),greater <>());
    }
    set<line>::iterator it1,it2;
    ll tmp2;
    dfs(0,n-1,it1,it2,tmp2);
    s.clear();
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R){
    n = sz(H);
    q = sz(L);
    res=vector <ll> (q,INF);
    for (ll i = 0;i < n;i ++)a[i] = H[i];
    for (ll i = 0;i < q;i ++){
        all_queries[i] = MP(L[i],R[i]);
    }
    solve();
    reverse(a,a+n);
    for (ll i = 0;i < q;i ++){
        all_queries[i] = MP(n-1-R[i],n-1-L[i]);
    }
    solve();
    return res;
}

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