Submission #900855

#	Time	Username	Problem	Language	Result	Execution time	Memory
900855		abcvuitunggio	Meetings (IOI18_meetings)	C++17	100 / 100	2406 ms	292092 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct line{
    long long a,b;
}a[750001];
vector <int> ql,qr,ve[750001],v;
vector <long long> h,res,ans;
set <int> s;
int n,q,mx[750001][20],lg[750001];
int f(int l, int r){
    int d=lg[r-l+1],x=mx[l][d],y=mx[r-(1<<d)+1][d];
    return (h[x]<h[y]?y:x);
}
long long calc(int i){
    int j=*s.lower_bound(i);
    return a[j].a*i+a[j].b;
}
long long dnc(int l, int r){
    if (l>r)
        return 0;
    if (l==r){
        a[l]={h[l],h[l]*(1-l)};
        s.insert(l);
        for (int i:ve[l])
            if (qr[i]<=r)
                ans[i]+=h[l];
        return 0;
    }
    int mid=f(l,r);
    long long x=dnc(l,mid-1),y=dnc(mid+1,r)+h[mid]*(mid-l+1),c=(mid>l?calc(mid-1):0)+x+h[mid];
    v.clear();
    v.push_back(mid);
    s.insert(mid);
    int last=mid;
    for (auto it=s.upper_bound(mid);it!=s.end()&&*it<=r;it++){
        int i=*it;
        if (h[mid]*i+c-h[mid]*mid<=a[i].a*i+a[i].b+y){
            v.push_back(i);
            last=i;
            continue;
        }
        last=(a[i].b+y-c+h[mid]*mid)/(h[mid]-a[i].a);
        break;
    }
    for (int i:v)
        s.erase(i);
    s.insert(last);
    a[last]={h[mid],c-h[mid]*mid-y};
    if (mid-l<r-mid+1){
        for (int i=l;i<mid;i++)
            a[i].b+=x-y;
        for (int i:ve[l])
            if (qr[i]>=mid&&qr[i]<=r)
                ans[i]+=calc(qr[i])+y;
        return y;
    }
    for (int i=mid;i<=r;i++)
        a[i].b+=y-x;
    for (int i:ve[l])
        if (qr[i]>=mid&&qr[i]<=r)
            ans[i]+=calc(qr[i])+x;
    return x;
}
void solve(){
    s.clear();
    for (int j=1;j<20;j++)
        for (int i=0;i+(1<<j)-1<n;i++){
            int l=mx[i][j-1],r=mx[i+(1<<(j-1))][j-1];
            mx[i][j]=(h[l]<h[r]?r:l);
        }
    for (int i=0;i<n;i++)
        ve[i].clear();
    for (int i=0;i<q;i++){
        int v=f(ql[i],qr[i]);
        ans[i]=h[v]*(v-ql[i]+1);
        if (v<qr[i])
            ve[v+1].push_back(i);
    }
    dnc(0,n-1);
    for (int i=0;i<q;i++)
        res[i]=min(res[i],ans[i]);
}
vector <long long> minimum_costs(vector <int> H, vector <int> L, vector <int> R){
    ql=L,qr=R,n=H.size(),q=L.size();
    for (int i:H)
        h.push_back(i);
    res.assign(q,1e18);
    for (int i=2;i<=n;i++)
        lg[i]=lg[i/2]+1;
    for (int i=0;i<n;i++)
        mx[i][0]=i;
    ans.assign(q,0);
    solve();
    reverse(h.begin(),h.end());
    for (int i=0;i<q;i++){
        ql[i]=n-ql[i]-1;
        qr[i]=n-qr[i]-1;
        swap(ql[i],qr[i]);
    }
    solve();
    return res;
}

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