Submission #329276

#	Time	Username	Problem	Language	Result	Execution time	Memory
329276		IloveN	Meetings (IOI18_meetings)	C++14	21 / 100	927 ms	259868 KiB

meetings

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e6+10;
const ll inf=1e18;
struct ds {int l,r,id;};
struct node
{
    vi lef,rig;
    int p_lef=0,p_rig=0;
};

int a[N],n,q,lg[N];
ds Q1[N],Q2[N];
ll ans[N],val1[N],val2[N];
pii spr[22][N*2];
node it[N*4];

void build2()
{
    stack<int> st;
    st.push(0);
    a[0]=a[n+1]=1e9+1;
    for (int i=1;i<=n;i++)
    {
        while (a[i]>=a[st.top()]) st.pop();
        val1[i]=val1[st.top()]+(ll)a[i]*(i-st.top());
        st.push(i);
    }
    while (st.size()) st.pop();
    st.push(n+1);
    for (int i=n;i;i--)
    {
        while (a[i]>a[st.top()]) st.pop();
        val2[i]=val2[st.top()]+(ll)a[i]*(st.top()-i);
        st.push(i);
    }
    int k=-1;
    for (int i=1;i<=n;i++)
    {
        if (i==(i&-i)) k++;
        lg[i]=k;
        spr[0][i]=mp(a[i],i);
    }
    for (int i=1;i<=20;i++)
        for (int j=1;j<=n;j++) spr[i][j]=max(spr[i-1][j],spr[i-1][j+(1<<(i-1))]);
}

int max_range(int l,int x)
{
    int k=lg[x-l+1];
    return max(spr[k][l],spr[k][x-(1<<k)+1]).se;
}

ll suf(int x,int l)
{
    int id=max_range(l,x);
    return val1[x]-val1[id]+(ll)a[id]*(id-l+1);
}

ll pre(int x,int r)
{
    int id=max_range(x,r);
    return val2[x]-val2[id]+(ll)a[id]*(r-id+1);
}

ll cost(int l,int r,int mid) {/*cout<<mid<<" "<<suf(mid,l)+pre(mid,r)-a[mid]<<"\n"*/;return suf(mid,l)+pre(mid,r)-a[mid]; }

bool cmp(pii l1,pii l2,pii l3,int typ)
{
    if ((ll)(l2.se-l1.se)*(l1.fi-l3.fi)==(ll)(l3.se-l1.se)*(l1.fi-l2.fi)) return true;
    if (typ) return (ll)(l2.se-l1.se)*(l1.fi-l3.fi)>(ll)(l3.se-l1.se)*(l1.fi-l2.fi);
    return (ll)(l2.se-l1.se)*(l1.fi-l3.fi)<(ll)(l3.se-l1.se)*(l1.fi-l2.fi);
}

void ins(vector<int> &vt,vector<pii> &line,ll slope,ll val,int x,int best_id,int typ)
{
    int siz=vt.size();
    pii new_line=mp(slope,val-slope*x); //slope*x+c=val c=val-slope*x
    while (vt.size()>1 && cmp(line[siz-2],line.back(),new_line,typ)) line.pop_back(),vt.pop_back();
    line.pb(new_line);
    vt.pb(best_id);
}

void build(int id,int l,int r)
{
    if (l==r)
    {
        it[id].lef.eb(l);
        it[id].rig.eb(r);
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    mid=max_range(l,r);
    vector<int> vt;
    vector<pii> line;
    ll val=cost(l,r,l),slope=-a[l],best_id=l;
    for (int i=l+1;i<=mid;i++)
        if (-a[i]>=slope)
        {
            ll new_val=cost(l,r,i);
            if (new_val<val) val=new_val,best_id=i;
        }
        else ins(vt,line,slope,val,l,best_id,1),slope=-a[i];
    ins(vt,line,slope,val,l,best_id,1);
    reverse(all(vt));
    it[id].lef=vt;
    vt.clear();
    line.clear();


    val=cost(l,r,r),slope=a[r],best_id=r;
    for (int i=r;i>=mid;i--)
        if (a[i]<=slope)
        {
            ll new_val=cost(l,r,i);
            if (new_val<val) val=new_val,best_id=i;
        }
        else ins(vt,line,slope,val,r,best_id,0),slope=a[i];
    ins(vt,line,slope,val,r,best_id,0);
    reverse(all(vt));
    it[id].rig=vt;
}

ll get1(int id,int l,int r,int u,int v)
{
    if (l>v || r<u) return inf;
    if (u<=l && r<=v)
    {
        ll val=cost(u,v,it[id].lef[it[id].p_lef]);
        while (it[id].p_lef<(int)it[id].lef.size()-1)
        {
            ll new_val=cost(u,v,it[id].lef[it[id].p_lef+1]);
            if (val<new_val) break;
            val=new_val;
            it[id].p_lef++;
        }
        return val;
    }
    int mid=(l+r)/2;
    return min(get1(id*2,l,mid,u,v),get1(id*2+1,mid+1,r,u,v));
}

ll get2(int id,int l,int r,int u,int v)
{
    if (l>v || r<u) return inf;
    if (u<=l && r<=v)
    {
        ll val=cost(u,v,it[id].rig[it[id].p_rig]);
        while (it[id].p_rig<(int)it[id].rig.size()-1)
        {
            ll new_val=cost(u,v,it[id].rig[it[id].p_rig+1]);
            if (val<new_val) break;
            val=new_val;
            it[id].p_rig++;
        }
        return val;
    }
    int mid=(l+r)/2;
    return min(get2(id*2,l,mid,u,v),get2(id*2+1,mid+1,r,u,v));
}

bool cmp1(ds t1,ds t2) {return t1.l>t2.l;}
bool cmp2(ds t1,ds t2) {return t1.r<t2.r;}

void process()
{
    build2();
    /*for (int i=1;i<=q;i++)
    {
        int l=Q1[i].l,r=Q1[i].r;
        ll res=inf;
        for (int t=l;t<=r;t++)
            res=min(res,cost(l,r,t));
        ans[i]=res;
    }*/
    build(1,1,n);
    //for (int x : it[1].lef) cout<<x<<"\n";
    sort(Q1+1,Q1+q+1,cmp1);
    sort(Q2+1,Q2+q+1,cmp2);
    for (int i=1;i<=q;i++) ans[i]=inf;
    for (int i=1;i<=q;i++) ans[Q1[i].id]=min(ans[Q1[i].id],get1(1,1,n,Q1[i].l,Q1[i].r));
    for (int i=1;i<=q;i++) ans[Q2[i].id]=min(ans[Q2[i].id],get2(1,1,n,Q2[i].l,Q2[i].r));
}

vll minimum_costs(vi v1,vi v2,vi v3)
{
    n=v1.size();
    q=v2.size();
    for (int i=1;i<=n;i++) a[i]=v1[i-1];
    for (int i=1;i<=q;i++) Q1[i]=Q2[i]={v2[i-1]+1,v3[i-1]+1,i};
    process();
    vll res;
    for (int i=1;i<=q;i++) res.eb(ans[i]);
    return res;
}

/*int main()
{
    freopen("meetings.inp","r",stdin);
    freopen("meetings.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    vi v1,v2,v3;
    for (int i=1,x;i<=n;i++) cin>>x,v1.eb(x);
    for (int i=1,l,r;i<=q;i++) cin>>l>>r,v2.eb(l),v3.eb(r);
    vll v4=minimum_costs(v1,v2,v3);
    for (ll x : v4) cout<<x<<" ";
    return 0;
}*/

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