Submission #1022739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022739		hotboy2703	Meetings (IOI18_meetings)	C++17	60 / 100	2076 ms	786432 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{
    ll a,b,r;
    ll eval(ll x,ll lazy){
        return a * x + b + lazy;
    }
};
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);
}
void dfs(ll l,ll r,deque <line> &s,ll &lazy){
    if (l > r)return;

    ll mid = max_id(l,r);
//    cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
    deque <line> L,R;
    ll wL=0,wR=0;
    dfs(l,mid-1,L,wL);
    dfs(mid+1,r,R,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 = L.back().eval(mid-1,wL) + a[mid] - a[mid] * mid;
    while (!R.empty()&&intersect(T,R.front(),wR) >= R.front().r){
        T.r = R.front().r;
        R.pop_front();
    }
    if (!R.empty()){
        T.r = max(T.r,intersect(T,R.front(),wR));
    }
//    cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
//    if (sz(L))cout<<"T "<<T.a<<' '<<T.b<<' '<<L.back().a<<' '<<L.back().b<<' '<<L.back().eval(mid-1)<<' '<<a[mid] - a[mid] * mid<<endl;
    if (mid-l+1>r-mid){
        swap(s,L);
        swap(lazy,wL);
        s.push_back({T.a,T.b - lazy,T.r});
        for (auto x:R){
            x.b += wR-lazy;
            s.push_back(x);
        }
    }
    else{
        swap(s,R);
        swap(lazy,wR);
        s.push_front({T.a,T.b - lazy,T.r});
        for (ll i = sz(L)-1;i>=0;i--){
            line x = L[i];
            x.b += wL-lazy;
            s.push_front(x);
        }
    }
//    cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
//    for (auto x:s){
//        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 + (*lower_bound(s.begin(),s.end(),y,[](line x,ll val){return x.r < val;})).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 <>());
    }
    deque <line> tmp;
    ll tmp2;
    dfs(0,n-1,tmp,tmp2);
}
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: 0 / 40