Submission #294561

#	Time	Username	Problem	Language	Result	Execution time	Memory
294561		IloveN	모임들 (IOI18_meetings)	C++14	0 / 100	5557 ms	245744 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]+a[id]*(id-l+1);
}

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

ll cost(int l,int r,int mid) {return suf(mid,l)+pre(mid,r)-a[mid]; }

/*ll cost(int l,int r,int mid)
{
    ll res=0;
    for (int i=l;i<=r;i++)
        if (i<=mid) res+=a[max_range(i,mid)];
        else res+=a[max_range(mid,i)];
    int val=0;
    for (int i=mid;i>=l;i--)
    {
        val=max(val,a[i]);
        res+=val;
    }
    val=a[mid];
    for (int i=mid+1;i<=r;i++)
    {
        val=max(val,a[i]);
        res+=val;
    }
    return res;
}*/

bool cmp(int a1,int b1,int a2,int b2,int a3,int b3)
{
    return (ll)(b2-b1)*(a1-a3)>=(ll)(b3-b1)*(a1-a2);
}

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<pll> vt; //fi*x+se
    for (int i=mid-1;i>=l;i--)
    {
        ll val=pre(i,r);
        int t=i;
        while (vt.size() && vt.back().fi>=-a[i])
        {
            if (vt.back().fi*(i+1)+vt.back().se+a[i]<val) val=vt.back().fi*(i+1)+vt.back().se+a[i],t=it[id].lef.back();
            vt.pop_back();
            it[id].lef.pop_back();
        }
        pii line=mp(-a[i],val+a[i]*i); //-a[i]*i+b=val b=val+a[i]*i
        while (vt.size()>1 && cmp(vt[(int)vt.size()-2].fi,vt[(int)vt.size()-2].se,vt.back().fi,vt.back().se,line.fi,line.se)) vt.pop_back(),it[id].lef.pop_back();
        vt.eb(line);
        it[id].lef.eb(t);
    }
    vt.clear();
    for (int i=mid+1;i<=r;i++)
    {
        ll val=suf(i,l);
        int t=i;
        while (vt.size() && vt.back().fi<=a[i])
        {
            if (vt.back().fi*(i-1)+vt.back().se+a[i]<val) val=vt.back().fi*(i-1)+vt.back().se+a[i],t=it[id].rig.back();
            vt.pop_back();
            it[id].rig.pop_back();
        }
        pii line=mp(a[i],val-a[i]*i); //a[i]*i+b=val b=val-a[i]*i
        while (vt.size()>1 && cmp(vt[(int)vt.size()-2].fi,vt[(int)vt.size()-2].se,line.fi,line.se,vt.back().fi,vt.back().se)) vt.pop_back(),it[id].rig.pop_back();
        vt.eb(line);
        it[id].rig.eb(t);
    }
}

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);
    sort(Q1+1,Q1+n+1,cmp1);
    sort(Q2+1,Q2+n+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("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    vll vt=minimum_costs({2,4,3,5},{0,1},{2,3});
    for (int x : vt) cout<<x<<"\n";
    return 0;
}*/

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