Submission #883131

#	Time	Username	Problem	Language	Result	Execution time	Memory
883131		andrei_boaca	Meetings (IOI18_meetings)	C++17	60 / 100	2997 ms	214384 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const ll INF=1e9;
typedef pair<ll,ll> pll;
ll n,q,v[100005],rmq[21][100005],loga[100005];
ll sdist[5005][5005];
int nxtL[100005],nxtR[100005],cL[21][100005],cR[21][100005],w[100005];
ll getmax(ll l,ll r)
{
    ll lg=loga[r-l+1];
    return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
ll getmin(ll l,ll r)
{
    ll lg=loga[r-l+1];
    return min(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
bool inside(int l,int r)
{
    return l>=1&&l<=n&&r>=1&&r<=n&&l<=r;
}
ll nrsecv=0;
struct date
{
    int l,r;
} secv[100005],mylft[100005][21],myrgt[100005][21];
set<pll> setik;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
    n=H.size();
    vector<ll> sol;
    q=L.size();
    ll hmax=0;
    for(int i=1;i<=n;i++)
    {
        v[i]=H[i-1];
        hmax=max(hmax,v[i]);
        for(int bit=0;bit<=20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    if(n<=5000&&q<=5000)
    {
        for(int i=n;i>=1;i--)
        {
            rmq[0][i]=v[i];
            for(int j=1;j<=20;j++)
            {
                rmq[j][i]=rmq[j-1][i];
                int poz=i+(1<<(j-1));
                if(poz<=n)
                    rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                ll st=min(i,j);
                ll dr=max(i,j);
                ll val=getmax(st,dr);
                sdist[i][j]=sdist[i][j-1]+val;
            }
        }
        for(int z=0;z<q;z++)
        {
            int l=L[z]+1;
            int r=R[z]+1;
            ll ans=1e18;
            for(int i=l;i<=r;i++)
                ans=min(ans,sdist[i][r]-sdist[i][l-1]);
            sol.push_back(ans);
        }
        return sol;
    }
    for(int i=0;i<q;i++)
        sol.push_back((int)1e9);
    deque<int> coada;
    for(int i=1;i<=n;i++)
    {
        while(!coada.empty()&&v[coada.back()]<=v[i])
            coada.pop_back();
        if(coada.empty())
            nxtL[i]=0;
        else
            nxtL[i]=coada.back();
        coada.push_back(i);
    }
    coada.clear();
    for(int i=n;i>=1;i--)
    {
        while(!coada.empty()&&v[coada.back()]<=v[i])
            coada.pop_back();
        if(coada.empty())
            nxtR[i]=n+1;
        else
            nxtR[i]=coada.back();
        coada.push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=hmax;j++)
            cL[j][i]=cR[j][i]=1e9;
        ll sum=0;
        ll poz=i;
        while(poz!=0)
        {
            ll val=v[poz];
            ll last=nxtL[poz];
            ll cst=-(n-poz)*val+sum;
            cL[val][i]=cst;
            sum+=val*abs(poz-last);
            poz=last;
        }
        sum=0;
        poz=i;
        while(poz<=n)
        {
            ll val=v[poz];
            ll last=nxtR[poz];
            ll cst=-(poz-1)*val+sum-v[i];
            cR[val][i]=cst;
            sum+=val*abs(poz-last);
            poz=last;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=hmax;j++)
        {
            mylft[i][j]={-1,-1};
            myrgt[i][j]={-1,-1};
        }
        int poz=i;
        while(poz<=n)
        {
            int val=v[poz];
            int last=nxtR[poz];
            mylft[i][val]={poz,last-1};
            poz=last;
        }
        poz=i;
        while(poz>=1)
        {
            int val=v[poz];
            int last=nxtL[poz];
            myrgt[i][val]={last+1,poz};
            poz=last;
        }
    }
    for(ll xL=1;xL<=hmax;xL++)
        for(ll xR=1;xR<=hmax;xR++)
        {
            for(int i=1;i<=n;i++)
                w[i]=cL[xL][i]+cR[xR][i];
            for(int i=n;i>=1;i--)
            {
                rmq[0][i]=w[i];
                for(int j=1;j<=17;j++)
                {
                    rmq[j][i]=rmq[j-1][i];
                    int poz=i+(1<<(j-1));
                    if(poz<=n)
                        rmq[j][i]=min(rmq[j][i],rmq[j-1][poz]);
                }
            }
            for(int z=0;z<q;z++)
            {
                int l=L[z]+1;
                int r=R[z]+1;
                bool ok=0;
                if(xL==4&&xR==3)
                    ok=1;
                int l1=mylft[l][xL].l;
                int r1=mylft[l][xL].r;
                int l2=myrgt[r][xR].l;
                int r2=myrgt[r][xR].r;
                if(inside(l1,r1)&&inside(l2,r2))
                {
                    l1=max(l1,l2);
                    r1=min(r1,r2);
                    if(inside(l1,r1))
                    {
                        int val=getmin(l1,r1)+(n-l+1)*xL+r*xR;
                        sol[z]=min(sol[z],1LL*val);
                    }
                }
            }
        }
    return sol;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:174:22: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  174 |                 bool ok=0;
      |                      ^~

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