Submission #525090

#	Time	Username	Problem	Language	Result	Execution time	Memory
525090		leaked	Meetings (IOI18_meetings)	C++14	60 / 100	5518 ms	245580 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"


#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+1;
const ll inf=1e9;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
struct node{
    int mx=0;
    vec<int> cntl,cntr;
    vec<int>dpl,dpr;
    node(){
        cntl.assign(21,0);cntr=cntl;
        dpl.assign(21,inf);dpr=dpl;
        mx=-1;
    }
};
node mg(node a,node b){
    node c;
    c.mx=max(a.mx,b.mx);
    vec<int>cost(21,0),pcnt(21,0);
    ll sm=0;
    for(int i=0;i<=20;i++) pcnt[i]=(i?pcnt[i-1]:0)+b.cntl[i],cost[i]=(i?cost[i-1]:0)+b.cntl[i]*i;
    sm=cost[20];
    for(int i=0;i<sz(a.dpl);i++){
        int x=pcnt[i]*i+a.dpr[i]+sm-cost[i];
        int y=pcnt[a.mx]*a.mx+a.dpl[i]+sm-cost[a.mx];
        umin(c.dpl[i],y);umin(c.dpr[c.mx],y);
        umin(c.dpr[max(i,b.mx)],x);umin(c.dpl[a.mx],x);
    }

    for(int i=0;i<=20;i++) pcnt[i]=(i?pcnt[i-1]:0)+a.cntr[i],cost[i]=(i?cost[i-1]:0)+a.cntr[i]*i;
    sm=cost[20];
    for(int i=0;i<sz(b.dpl);i++){
        int x=pcnt[i]*i+b.dpl[i]+sm-cost[i];
        int y=pcnt[b.mx]*b.mx+b.dpr[i]+sm-cost[b.mx];
        umin(c.dpr[i],y);umin(c.dpl[c.mx],y);
        umin(c.dpl[max(i,a.mx)],x);umin(c.dpr[b.mx],x);
    }

    for(int i=0;i<=20;i++){
        c.cntr[max(i,b.mx)]+=a.cntr[i];
        c.cntr[i]+=b.cntr[i];
        c.cntl[max(i,a.mx)]+=b.cntl[i];
        c.cntl[i]+=a.cntl[i];
    }
    return c;
}
node t[4*N];
int a[N];
node emp;
void build(int v,int tl,int tr){
    if(tl==tr){
        t[v].cntl[a[tl]]=1;
        t[v].cntr[a[tl]]=1;
        t[v].mx=a[tl];
        t[v].dpl[a[tl]]=a[tl];
        t[v].dpr[a[tl]]=a[tl];
    }
    else{
        int tm=(tl+tr)>>1;
        build(v<<1,tl,tm);build(v<<1|1,tm+1,tr);
        t[v]=mg(t[v<<1],t[v<<1|1]);
    }
}
node get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r)
        return t[v];
    if(tl>r||tr<l)
        return emp;
    int tm=(tl+tr)>>1;
    return mg(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
vec<ll> minimum_costs(vec<int> a,vec<int> l,vec<int> r){
    int q=sz(l);
    vec<ll>ans(q);
    int n=sz(a);
    for(int i=0;i<n;i++) ::a[i]=a[i];
    bool ok=(*max_element(all(a))<=20);
    if(ok)
        build(1,0,n-1);
    vec<int>lft(n),rgt(n);
      vec<pii>st;
      st.pb({2e9,-1});
      for(int i=0;i<n;i++){
        while(sz(st) && a[i]>st.back().f){
            rgt[st.back().s]=i-1;
            st.pop_back();
        }
        lft[i]=st.back().s+1;
        st.pb({a[i],i});
      }
      while(sz(st)>1) rgt[st.back().s]=n-1,st.pop_back();
    const ll infq=1e18;
      auto stupid=[&](int l,int r){
            int mx=-2e9;
            vec<ll> pref(n+1,0);
            for(int i=l;i<=r;i++){
                int l1=i,r1=min(r,rgt[i]);
                ll cst=1ll*a[i]*(i-max(lft[i],l)+1);
                pref[l1]+=cst;pref[r1+1]-=cst;
    //            cout<<"ALO "<<l1<<' '<<r1<<' '<<cst<<endl;
                l1=max(l,lft[i]),r1=i;
                cst=1ll*a[i]*(min(rgt[i],r)-i+1);
    //            cout<<"ALO "<<l1<<' '<<r1<<' '<<cst<<endl;

                pref[l1]+=cst;pref[r1+1]-=cst;
                pref[i]-=a[i];pref[i+1]+=a[i];
            }
            for(int i=1;i<=n;i++) pref[i]+=pref[i-1];
            ll ans=infq;
            int j=l;
            int j1=l;
            for(int i=l;i<=r;i++){
                if(a[i]<a[j]) j=i;
                if(a[i]>a[j1]) j1=i;
                ans=min(ans,pref[i]);
    //            cerr<<"DBG "<<a[i]<<' '<<pref[i]<<'\n';
            }
    //        cout<<endl;
            return ans;
      };
    for(int i=0;i<q;i++){
        if(ok){
            ans[i]=inf;
            node me=get(l[i],r[i],1,0,n-1);
            for(auto &z : me.dpl) umin(ans[i],(ll)z);
            for(auto &z : me.dpr) umin(ans[i],(ll)z);
        }
        else
            ans[i]=stupid(l[i],r[i]);
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In lambda function:
meetings.cpp:109:17: warning: unused variable 'mx' [-Wunused-variable]
  109 |             int mx=-2e9;
      |                 ^~

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