Submission #1022813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022813		hotboy2703	Meetings (IOI18_meetings)	C++17	0 / 100	60 ms	25552 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;}

    ll mid = max_id(l,r);
//    cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
    set<line>::iterator Lb,Lf,Rb,Rf;
    ll wL=0,wR=0;
    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<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
//    if (l==7&&r==11&&mid==9)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 != s.end();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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40